Find first and last set bit of a long integer: Difference between revisions
Content added Content deleted
Line 237: | Line 237: | ||
42**5 = 130691232(x07ca30a0): M x04000000(26) L x020( 5) |
42**5 = 130691232(x07ca30a0): M x04000000(26) L x020( 5) |
||
</pre> |
</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}}== |
=={{header|J}}== |