Menu
Consider this link from the Bit Twiddling Hacks website. In order to count the trailing bits, the following algorithm is used:
unsigned int v; // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v); /* THIS LINE */
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;
Can someone explain me the role of the line marked as /* THIS LINE */ and more importantly is it possible to use only bitwise operations to avoid the use of signed() ?
EDIT: How to replace signed() by arithmetic/logical/bitwise operations?
262
Given an integer, count the number of trailing zeroes. For example, for n = 12, its binary representation is 1100 and number of trailing zero bits is 2. Examples : Input : 8 Output : 3 Binary of 8 is 1000, so there are three trailing zero bits.
The position of zeros after first one from the least significant bit (LSB) is called as trailing zeros in binary number.
A bitwise XOR is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only one of the bits is 1, but will be 0 if both are 0 or both are 1.
Setting a bitUse the bitwise OR operator ( | ) to set a bit. number |= 1UL << n; That will set the n th bit of number . n should be zero, if you want to set the 1 st bit and so on upto n-1 , if you want to set the n th bit.
v &= -signed(v) will clear all but the lowest set bit (1-bit) of v, i.e. extracts the least significant 1 bit from v (v will become a number with power of 2 afterwards). For example, for v=14 (1110), after this, we have v=2 (0010).
Here, using signed() is because v is unsigned and you're trying to negate an unsigned value (gives compilation error with VS2012) (comment from JoelRondeau). Or you will get a warning like this: warning C4146: unary minus operator applied to unsigned type, result still unsigned (my test).
108
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
