CODEWITHSUNDEEP
bit-manipulation
QuantumRich
QuantumRich

Reputation: 886

Bit shifting until first '1' in a bit string

Is there a way to shift my bit string until I hit the first 1 as my least significant bit? e.g.

0001000100 right shifts twice to 0000010001
0100001010 right shifts once to 0010000101
0010000000 right shifts seven times to 0000000001

I am trying to do this with a bitwise operation.

Upvotes: 2

Views: 1855

Answers (2)

user555045
user555045

Reputation: 64904

Alternatively, you can count the number of trailing bits and then shift by that. No branches, and scales logarithmically in the bitwidth. For example for 32 bits:

t = ~x & (x - 1)  # mask where all the trailing zeroes are now 1s
c = t - ((t >> 1) & 0x55555555)  # count 1s in the mask
c = (c & 0x33333333) + ((c >> 2) & 0x33333333)
c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F)
c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF)
c = (c & 0x0000FFFF) + ((c >> 16) & 0x0000FFFF)
result = x >> c   # shift right by the number of trailing zeroes

For 64 bits you'd need one more reduction step.

In hardware, you could do a popcnt more efficiently, with a depth of O(log n) (implementing this naively gives O(log2 n) because you'd have log n adders each of depth O(log n)). The first and last step obviously also have a logarithmic depth.

For software, check your CPU for bsf, tzcnt, popcnt, or some equivalent, to do something like:

x >> __builtin_ctz(x)
or
x >> __popcnt(~x & (x - 1))

Often the result for something like ctz(0) will be undefined, but shifting zero by any amount won't change it anyway, so it doesn't matter. If there is no such instruction, see the first codeblock for how to work around that.

It may seem attractive to literally divide (with an actual division) by the highest power of 2 that goes into x:

x / (x & -x)

But that's horrible, don't do it. Even apart from the fact that x = 0 now gets your intro trouble, division is a terrible thing that you should avoid at almost any cost.

Upvotes: 2

Geoduck
Geoduck

Reputation: 9005

If n is an unsigned int of some kind:

while ( (n & 0x1) == 0) n >>= 1;

Upvotes: 5

Related Questions