Count the consecutive zero bits (trailing) on the right in parallel: an explanation?

▲
5
▼

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?

c++
algorithm
c++11
bit-manipulation
asked on Stack Overflow Jan 23, 2014 by Vincent • edited Jan 23, 2014 by Vincent

5 Answers

▲
5
▼

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).

answered on Stack Overflow Jan 23, 2014 by herohuyongtao • edited Jan 23, 2014 by herohuyongtao
▲
0
▼

The expression v &= -signed(v), is ANDing the the number and the negative of that number itself. So we are performing a binary AND on the number and the two's complement representation of the number

answered on Stack Overflow Jan 23, 2014 by sajas
▲
0
▼

Following what i understood from the code :-

AND v with its 2's complement :- sets all digits after the first 1 from right to 0

Example :- v = 10101000 then -v = ~v + 1 (1's complement plus 1) = 01010111 + 1 =01011000
v&-v = 10101000 & 01011000 = 00001000

answered on Stack Overflow Jan 23, 2014 by Vikram Bhat
▲
0
▼

There's no simple bitwise operation to do -signed(v). Addition and subtraction require "carries", operations on bit X may affect bit X+1. So, it takes arithmetic.

But basically, unary -x is just binary 0-x, so you can use standard arithmetic if you don't have a direct negation operation.

answered on Stack Overflow Jan 23, 2014 by MSalters
▲
0
▼

signed in this code is an error which causes undefined behavior.

It can be safely removed. The code requires the behavior of unsigned negation... which signed negation may or may not deliver. Without the keyword the behavior is always as expected.

Now, the code still is not portable. But at least it will be safe, and it will work if int is 32 bits.

answered on Stack Overflow May 27, 2019 by Ben Voigt

User contributions licensed under CC BY-SA 3.0