Bitwise High Bit

Question

I want to find the most significant bit that is set to 1 . I tried everything possible from & to ORing all bits from 1 to 31 and it does not work.

As if 1000000 I would like to have 7 .

Answer 1

If you insist on using bitwise operators directly, you can try something like this:

 private int mostSignificantBit(int myInt){ int mask = 1 << 31; for(int bitIndex = 31; bitIndex >= 0; bitIndex--){ if((myInt & mask) != 0){ return bitIndex; } mask >>>= 1; } return -1; } 

We initialize the mask 1 << 31 , because it represents 1, followed by 31 0. We use this value to check if index 31 (32nd place) is 1. When we and this value with myInt , we get 0 if the corresponding bit is not set to myInt . If so, we return that bitIndex . If not, we will move the mask to the right by 1 and try again. We repeat until we work out the place for the change, in which case this means that none of the bits have been set (perhaps you want to throw an exception here instead of returning -1).

Note that this will return a value of 0 for 1 and 6 for 64 ( 1000000 in binary format). You can customize this if you want. Note also that I used the unsigned operator on the right, and not the signed shift to the right. This is because the goal here is to process the source bits and not their signed interpretation, but in this case it does not matter, since all negative values ​​end in the first iteration of the loop before the transition occurs.

Answer 2

http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Integer.html#numberOfLeadingZeros%28int%29 You want something like 32 - Integer.numberOfLeadingZeros(value) .

Answer 3

Although there is an accepted answer, I have another way to share what seems easier to me.

If you want to use bitwise operations, here is the way. Basically, I shift the right integer until it becomes zero. No mask required.

 private static int mostSignificantBit(int myInt){ int i = 0; while (myInt != 0) { ++i; myInt >>>= 1; } return i; } 

Another way is mathematical calculation:

 private static int mostSignificantBit(int myInt){ if (myInt == 0) return 0; // special handling for 0 if (myInt < 0) return 32; // special handling for -ve return (int)(Math.log(myInt)/Math.log(2)) +1; } 

Answer 4

The smoothed implementation I came across is three iterations and a table lookup.

 unsigned int msb32(unsigned int x) { static const unsigned int bval[] = { 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 }; unsigned int base = 0; if (x & 0xFFFF0000) { base += 32/2; x >>= 32/2; } if (x & 0x0000FF00) { base += 32/4; x >>= 32/4; } if (x & 0x000000F0) { base += 32/8; x >>= 32/8; } return base + bval[x]; } 

Answer 5

Sequential approximation minimizes iterations up to five cycles:

 unsigned int mostSignificantBit(uint32_t val) { unsigned int bit = 0; /* 4 = log(sizeof(val) * 8) / log(2) - 1 */ for(int r = 4; r >= 0 ; --r) { unsigned shift = 1 << r; /* 2^r */ uint32_t sval = val >> shift; if (sval) { bit += shift; val = sval; } } return bit; } 

Answer 6

Just use the numberOfTrailingZeros (value) method of the Long or Integer class.

Answer 7

Not the most efficient, perhaps, but this should work:

 public int firstBit(int i) { return i < 0 ? 31 : i == 0 ? 0 : Integer.toString(i, 2).length(); } 

Answer 8

For Little End format:

 ((yourByte & yourBitMask) >> msbIndex) && 0x01 

Answer 9

Just add another approach.

 public static int mostSignificantBit(int b) { for (int i = 1 << 30, j = 0; i > 0; i /= 2, j++) { if ((b & i) > 0) { return 31-j; } } return -1; } 

Answer 10

 if( value | 0x40 ) return 7; else if( value | 0x20 ) return 6; else if( value | 0x10 ) return 5; else if( value | 0x8 ) return 4; else if( value | 0x4 ) return 3; else if( value | 0x2 ) return 2; else if( value | 0x1 ) return 1;