Get length of bits used in int

Question

If you have the binary number 10110 how can I get it to return 11111? e.g a new binary number that sets all bits to 1 after the first 1, there are some likewise examples listed below:

101 should return 111 (3 bit length) 011 should return 11 (2 bit length) 11100 should be return 11111 (5 bit length) 101010101 should return 111111111 (9 bit length)

How can this be obtained the easiest way in Java? I could come up with some methods but they are not very "pretty".

Answer 1

Haven't tested, but something like this should be okay:

long setBits(long number) {
  long n = 1;
  while (n <= number) n <<= 1;
  return n - 1;
}

Answer 2

You could use this code:

int setBits (int value)
{
    value |= (value >> 1);
    value |= (value >> 2);
    value |= (value >> 4);
    value |= (value >> 8);
    value |= (value >> 16);
    return value;
}

The idea is that leftmost 1 will get copied to all positions on the right.

EDIT: Also works fine with a negative value. If you replace int with long, add one extra |= statement: value |= (value >> 32). In general, last shift must be a power of 2 that is at least half of value size in bits.

Answer 3

Once you know the "length" l, or ceiling (log base 2 (n)), of n, then (1<here.

Answer 4

Not most efficient, but simplest,

    int i = (1 << (int)(Math.log(n)/Math.log(2)+1)) - 1;

It will work for first 31 bit of int and first 63 bit for long.

Answer 5

My try: Integer.highestOneBit(b) * 2 - 1