Clear Lowest Bit
by Isai Damier, Android Engineer @ Google
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | /*************************************************************************** * Author: Isai Damier * Title: Clear Lowest Bit * Project: geekviewpoint * Package: algorithms * * Statement: * Clear the least significant (set) bit in the given sequence of bits. * * Sample Input: integer representation of bit sequence 1111111110 * Sample Output: 1111111100 after clearing the lowest set bit * * Technical Details: When counting in binary, the difference * between two consecutive numbers (i.e. n and n-1) is twofold: * 1] The least significant set bit in the greater number * is not set in the lesser number. * 2] All bits to the left of said least significant set bit * are the same for both numbers. * (7) 0000_0111, (6) 0000_0110, (5) 0000_0101, (4) 0000_0100, * (6) 0000_0110, (5) 0000_0101, (4) 0000_0100, (3) 0000_0011. * * Hence, taking the bitwise AND of n and n-1 is sufficient for * clearing the least significant bit. * **************************************************************************/ public int clearLowestBit(int n) { return n & (n - 1);} |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | import org.junit.Test;import static org.junit.Assert.*;public class BitwiseTest { /** * Test of clearLowestBit method, of class Bitwise. */ @Test public void testClearLowestBit() { Bitwise bits = new Bitwise(); System.out.println(""clearLowestBit""); String[] set = {""1111111111"", ""1111111110"", ""1111111100"", ""1111111000"", ""1111110000"", ""1111100000"", ""1111000000"", ""1110000000"", ""1100000000"", ""1000000000"", ""000000000"", ""000000000""}; int x, y; for (int i = 1; i < set.length; i++) { x = Integer.parseInt(set[i - 1], 2); y = Integer.parseInt(set[i], 2); assertEquals(y, bits.clearLowestBit(x)); } }} |
