Author: Gerd Isenberg
Date: 14:07:51 09/21/05
Go up one level in this thread
>Hi Andrew, > >first, for masking the least significant one bit, you can use x & -x instead of >((x^(x-1))+1) >> 1. ((x^(x-1))+1) >> 1 is even wrong, because it doesn't work if MSB is exclusively set (INT*MIN), let say 0x80000000 for a 32-bit int: x 0x80000000 x-1 0x7fffffff ^ 0xffffffff +1 0x00000000 ; oups, overflow >>1 0x00000000 therefore first shift the right-aligned binary one-sequence logical right to avoid the inc overflow: ((x^(x-1))>>1) + 1 x 0x80000000 x-1 0x7fffffff ^ 0xffffffff >>1 0x7fffffff +1 0x80000000 ; the correct, single isolated LS1B As already mentioned x & -x does the same job, while x & (x-1) resets the LS1B. Therefore following expressions are equivalent with two's complement arithmetic: (1) x & -x (2) x & (~x+1) (3) x & ~(x-1) (4) x ^ (x & (x-1)) (5) ((x ^ (x-1))>>1) + 1 (5) (x ^ (x-1))/2 + 1 > >For masking the most significant one bit, there is the O(ld N) parallel prefix >approach to set all lower bits, eg. for N = 64: > > x |= x >> 1; > x |= x >> 2; > x |= x >> 4; > x |= x >> 8; > x |= x >> 16; > x |= x >> 32; > ms1bmask = (x>>1) + 1; You already mentioned the parallel prefix fill to LSB in your posting, but your final return statement was wrong for the same reason - that (unsigned)-1 + 1 does overflow. Shift right before add. Gerd
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.