Bit Manipulation

0

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 in terms of divisor*quotient + modulus would be:
n = 16 * 19 + 7
thus modulus m = 7
311 = 1 0011 0111 in binary
1 0011 0111 = 1 0011 0000 + 0111
= 24*1 + 25*1 + 26*0 + 27*0 + 28*1 + 0111
= 24(20*1 + 21*1 + 22*0 + 23*0 + 24*1) + 0111
= 24(10011) + 0111
n = d*q + m where d =24, q = 10011, m = 0111
If d=2x, 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 & (2x – 1)

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

Leave A Reply