turning off leftmost non zero bit of a number

Question

how can I turn off leftmost non-zero bit of a number in O(1)?

for example

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

then after turning the leftmost non-zero bit off ,number looks like = 001101110

n will always be >0

Answer 1

Well, if you insist on O(1) under any circumstances, the Intel Intrinsics function _bit_scan_reverse() defined in immintrin.h does a hardware find for the most-significant non-zero bit in a int number.

Though the operation does use a loop (functional equivalent), I believe its constant time given its latency at fixed 3 (as per Intel Intrinsics Guide).

The function will return the index to the most-significant non-zero bit thus doing a simple:

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

should do.

This intrinsic is undefined for n == 0. So you gotta watch out there. I'm following the assumption of your original post where n > 0.

Answer 2

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

Your highest set bit is x.

So in order to reset that 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;
}

Answer 3

Check out this question, for a possibly faster solution, using a processor instruction.

However, an O(lgN) solution is:

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

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

Answer 4

If ANDN is not supported and LZCNT is supported, the fastest O(1) way to do it is not something along the lines of n = n & ~(1 << _bit_scan_reverse(n)); but rather...

int reset_highest_set_bit(int x)
{
    const int mask = 0x7FFFFFFF; // 011111111[...]

    return x & (mask >> __builtin_clz(x));
}