Set all bits up to given highest bit

Question

If I have a binary number, say x = 00010000, I can set all bits up to the highest and only set bit by doing y = x | (x - 1) resulting in y = 00011111.

How can I achieve the same result if multiple bits are set, e.g. x = 00010101?

http://stackoverflow.com/questions/53161/find-the-highest-order-bit-in-c http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i http://stackoverflow.com/questions/2589096/find-most-significant-bit-left-most-that-is-set-in-a-bit-array ... — phuclv, Aug 13 '14 at 16:36

score 1 · Accepted Answer · answered Aug 13 '14 at 16:34

This is a find first set problem

No possible solution with only bitwise operations. If you want to code it the usual way, think "binary search" for more efficient algorithms.

Here's something to get you started but I am sure there are more efficient algos out there

int findfirstset(unsigned int x) {
    x |= (x >>  1);
    x |= (x >>  2);
    x |= (x >>  4);
    x |= (x >>  8);
    x |= (x >> 16);
    return x - (x >> 1);
}

From there you could do your operation:

y = x | (x - 1)

Why bother with `x - (x >> 1)` and `y = x | (x - 1)`? After `x |= (x >> 16);` you already have the result desired by OP. — Apriori, Aug 13 '14 at 23:03

Set all bits up to given highest bit

1 Answers1