Removing first bit

Question

Is there an efficient way to remove the first bit of a number in C++ / Python, assuming you don't know how large the number is or its datatype?

I know in Python I can do it by getting the bin(n), truncating the string by 1, and then recasting it to an int, but I am curious if there is a more "mathematical" way to do this.

e.g. say the number is 6, which is 110 in binary. Chop the first bit and it becomes 10, or 2.

Answer 1

There's a bit twiddling hack to remove a bit at a time until only the uppermost is left:

def upper_bit(x):
    while x & (x - 1):
        x &= x - 1
    return x

Now you can use that as a mask:

def mask_off(x, mask):
    return x & ~mask

>>> mask_off(6, upper_bit(6))
2

Note that this only works for positive numbers, because of the boundless nature of Python ints.

Answer 2

looking at 110 (6 decimal)

The Most Significant bit is 100 (4 decimal) // -- Note that this is always a power of 2

Create a mask: one less than the MSB is 011 (3 decimal)

Mask off the highest bit using bitwise-and: 110 & 011 = 10 (2 decimal)

Calculating the MSB (Most Significant Bit) has been handled here and elsewhere quite often

Answer 3

Well, you could create a loop in which you would double some variable (say x) in each iteration and then check whether this variable is greater than your number. If it is, divide it by two and subtract from your number. For example, if your number is 11:

-first iteration: x=1<11, so continue

-second iteration: x =2<11, so continue

-third iteration: x=4<11, so continue

-fourth iteration: x=8<11, so continue

-fifth iteration: x=16>11, so divide x by two: x=8. Then subtract 8 from your number and get answer:

11-8=3.

Answer 4

If you using a C compiler that supports __builtin_clz, and you limit yourself to the type that __builtin_clz supports, you can do:

unsigned int chopWithBuiltin(unsigned int x) {
  //get number of leading redundant sign bits,
  //which is one less than the position of the MSB
  int msb_idx = __builtin_clz(x);
  //now make a mask that is all the bits below the MSB
  int mask = UINT_MAX >> (msb_idx+1);
  return x & mask;
}

This uses __builtin_clz which hopefully maps to something fast in assembly instead of a loop to detect the MSB.

For negative numbers you can build something similar with __builtin_clrsb but it gets complicated.