Anonymous user
Find first and last set bit of a long integer: Difference between revisions
Find first and last set bit of a long integer (view source)
Revision as of 05:48, 10 December 2011
, 12 years ago→Icon and Unicon
Line 237:
42**5 = 130691232(x07ca30a0): M x04000000(26) L x020( 5)
</pre>
=={{header|Icon}} and {{header|Unicon}}==
The task definition makes some assumptions that don't work in Icon/Unicon and are going to require some reinterpretation. In Icon/Unicon all integers appear to be implemented as a single common type. A specific implementation may or may not have large integers, but if it does they are essentially indistinguishable from regular integers. Given this implementing "efficient" procedures for the platform word size without loops or recursion makes little sense. Instead these lsb and msb routines are generalized to reduce the integer in blocks of bits and then zoom in on the desired bit by binary search (i.e. successively looking a blocks that are half the size again).
<lang Icon>link printf,hexcvt
procedure main()
every B := [42,2^32-1] | [1302,2^64-1] do {
base := B[1]
lim := B[2]
fmt := sprintf("%%i^%%i = %%%is (x%%0%is) : MSB=%%s LSB=%%s\n",*lim,*hexstring(lim))
every e := seq(0) do {
if (i := base^e) > lim then break
printf(fmt,base,e,i,hexstring(i),msb(i)|"-",lsb(i)|"-")
}
}
end
procedure msb(i) #: return the most significant set bit index or fail
static mask
initial mask := xsb_initial()
if i > 0 then {
b := 0
every m := mask[j := 1 to *mask by 2] & r := mask[j+1] do {
repeat {
l := iand(i,m)
i := ishift(i,r)
if i = 0 then break
b -:= r
}
i := l
}
return b
}
end
procedure lsb(i) #: return the least significant set bit index or fail
static mask
initial mask := xsb_initial()
if i > 0 then {
b := 0
every m := mask[j := 1 to *mask by 2] & r := mask[j+1] do
until iand(i,m) > 0 do {
i := ishift(i,r)
b -:= r
}
return b
}
end
procedure xsb_initial() #: setup tables for lsb/msb
static mask
initial { # build
mask := []
p := 32 * 2
until (p := p / 2) = 0 do put(mask,2^p-1,-p)
}
return mask # return pre-built data
end</lang>
{{libheader|Icon Programming Library}}
[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icn provides formatting]
[http://www.cs.arizona.edu/icon/library/src/procs/hexcvt.icn hexcvt.icn provides hexstring]
Output:<pre></pre>
=={{header|J}}==
| |||