Clever Geek Handbook

Turn off the left non-zero bit of a number

how can I turn off the bit to the left of a non-zero

number in O(1)

?

eg

n = 366 (base 10) = 101101110 (in base 2)

then after turning the leftmost non-zero

bit, the number looks like001101110

n will always be> 0

+3


source to share


3 answers


n = 2^x + y. x = log(n) base 2

Most significant bit of a bit x

.

So, to reset this bit, number &= ~(1 << x);



Another approach:

int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >> 1);
}

int main() {
    int n = 32767;
    int z = highestOneBit(n); // returns the highest set bit number i.e 2^x.
    cout<< (n&(~z)); // Resets the highest set bit.
    return 0;
}
+2


source


Well, if you insist on O(1)

under no circumstances, the Intel Intrinsics function _bit_scan_reverse()

defined in immintrin.h

finds the hardware for the most significant non-zero bit in the int number.

Although the operation uses a loop (functional equivalent), I believe its constant time gave it a delay at a fixed 3 (according to Intel Intrinsics Guide ).

The function will revert the index to the most significant non-zero bit, making it simple like this:



n = n & ~(1 << _bit_scan_reverse(n));

...

This is undefined internally for n == 0. So, you should watch out for it. I am following the assumption of your original post where n> 0.

+1


source


Review this question for a possible faster solution using the processor instruction.

However, the O (lgN) solution is:

int cmsb(int x)
{
    unsigned int count = 0;
    while (x >>= 1) {
        ++count;
    }

    return x & ~(1 << count);
}
0


source






More articles:


All Articles