Bit Manipulation

This article documents some of the instances where we use Bit manipulation techniques.

Convert byte to int

    public void testByteToIntByAndOperation() {
        byte byteValue = -87;
        int intValue = 0xFF & byteValue;
        assertEquals(169, intValue);
    }

Calculate power of 2 using right shift

    public void testPowerOf2ByRightShift() {
        assertEquals(8, 1 << 3);
    }

Find a power of 2 >= the given int input

    public void testFindPowerOf2GreaterThanGivenInt() {
        int someInt = 15;
        int powerOf2GreaterThanSomeInt = 1;
        while (powerOf2GreaterThanSomeInt < someInt)
            powerOf2GreaterThanSomeInt <<= 1;
        assertEquals(16, powerOf2GreaterThanSomeInt);
    }

Swap two numbers

public void testSwapUsingXor() {
        int old_a = 89;
        int old_b = 98;
        int a = old_a;
        int b = old_b;
        a ^= b;
        b ^= a;
        a ^= b;
        assertEquals(old_b, a);
        assertEquals(old_a, b);
    }

Compute modulus division by a power-of-2-number 

Suppose n=311 and d=16 n = 16 * 19 + 7 thus m = 7 311 = 1 0011 0111 in binary 1 0011 0111 = 1 0011 0000 + 0111 = 2⁴*1 + 2⁵*1 + 2⁶*0 + 2⁷*0 + 2⁸*1 + 0111 = 2⁴(2⁰*1 + 2¹*1 + 2²*0 + 2³*0 + 2⁴*1) + 0111 = 2⁴(10011) + 0111 n = d*q + m where d =2⁴, q = 10011, m = 0111 Thus if d=2^x, the modulus is the lower x bits of n We can obtain these lower bits by doing & operation m = 0111 = 1 0111 0111 & 1111 Thus m = n & (2^x - 1)

public void testFindModulusByAND() {
        int n = 311;
        int d = 1 << 4;
        int m = 7;
        assertEquals(m, n & (d -1));
    }

Home