The Inverse of a bit-shift to the left in the format 1 << n

Question

Let's say I have the following bit masks:

1 << 1, // 2
1 << 2, // 4 
1 << 3, // 8 
1 << 4, // 16 
1 << 5, // 32 
1 << 6  // 64

I would like to get the 'inverse'.

This does the job:

void foo(int n) {
  int c = 1;
  while (n/2 >= 2) {
    n /= 2;  
    c++;;
  }
  println(c);
}

For example, 1 << 4 resulted in 16. If I run foo(16) it prints 4. However, I feel like it could be done a lot simpler, but I can't figure out how.

Is it possible?

[Integer.numberOfLeadingZeros](http://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html#numberOfLeadingZeros-int-) can be used to get the position of the 1 bit, and its javadoc even has a couple of useful formulae with logarithms. — Oleg Estekhin, Jul 23 '15 at 16:08
possible duplicate of [Position of least significant bit that is set](http://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set) — talex, Jul 23 '15 at 16:13
@talex thanks, I would never have found that topic without knowing the terminology. — clankill3r, Jul 23 '15 at 16:19

score 2 · Answer 1 · answered Jul 23 '15 at 16:27

2

BigInteger has many useful methods - including getLowestSetBit(). It probably does it as fast as it can possibly be done.

public void test() {
    System.out.println(BigInteger.valueOf(16).getLowestSetBit());
}

answered Jul 23 '15 at 16:27

OldCurmudgeon

64,482
16
119
213

score 1 · Answer 2 · answered Jul 23 '15 at 16:16

1

void foo(int n)
{
    println( (Math.log(n) / Math.log(2))); 
    //cast to int with (int) to take off decimal place
}

Returns the "inverse" bitshift as you are calling it, the base 2 logarithm.

answered Jul 23 '15 at 16:16

Adam

2,422
18
29

Thanks, this works, but in the duplicate I saw a awesome technical post for a really fast solution :) – clankill3r Jul 23 '15 at 16:20
Okay! Glad I could help :) – Adam Jul 23 '15 at 16:27
Can you provide an example in which it is not? – Adam Jul 23 '15 at 17:02
I can't. I just have strange filling when use floating point arithmetic for bit manipulation :) – talex Jul 23 '15 at 17:07

talex · Answer 3 · 2015-07-23T17:02:13.527

1

Slightly faster and not depend on value itself.

UPDATED version

private static int foo2(int value) {
    int result = 0;

    int mask = 0xFFFF;
    int shift = 1<<4;
    for (int j = 0; j < 5; j++) {
        result <<= 1;
        if ((value & mask) == 0) {
            result |= 1;
            value >>>= shift;
        }
        shift >>>= 1;
        mask >>= shift;
    }
    return result;
}

edited Jul 23 '15 at 17:02

answered Jul 23 '15 at 16:55

talex

17,973
3
29
66

The Inverse of a bit-shift to the left in the format 1 << n

3 Answers3