Bit utils - bit manipulation and bit magic

AAA_Bit_Utils.txt

Bit utils - bit manipulation and bit magic 

BitUtils.java

package com.blogspot.groglogs.bitutils;

import com.blogspot.groglogs.structures.Pair;

public class BitUtils {

    /*
    Returns the lowest bit set to 1 in the given number
    The bit position (if counting from 0) is result - 1. 0 Would have no lowest set bit, therefore check for position -1!
    Magic formula!
    n - 1 creates a mask where the last bit set to 1 is now 0
    negating that mask gives us a new mask that is the exact opposite of n except for the bit we flipped before
    the AND operation of the original number with this mask, will return only the bit we flipped
    */
    public static long getLowestSetBit(long n){
        return n & ~(n - 1);
    }

    public static long getLowestSetBitPosition(long n){
        return getLowestSetBit(n) - 1;
    }

    /*
    Finds the lowest set bit and right propagates it
    We can bitwise OR the number with the position of its lowest set bit
    to mask the right portion with all 1
    */
    public static long rightPropagateLowestSetBit(long n){
        if(n > 1) return n | getLowestSetBitPosition(n);
        return n;
    }

    /*
    Calculate the modulus of n with a power of 2.
    The result is all the bits in n that are on the right from the position
    of the only set bit in the modulus
    */
    public static long moduloPower2(long n, long mod){
        //mod - 1 creates a mask of all the bits we want, so we can bitwise AND with the number to extract them only
        return n & (mod - 1);
    }

    /*
    Test if a number is a power of 2. 0 is never a power of anything
    A power of 2 will have only one bit set, so find the lowest set bit in n and XOR with n.
    If there was only one, we erased it and are left with 0, thus the number is a power of two
    */
    public static boolean isPower2(long n){
        if(n == 0) return false;
        return (n ^ getLowestSetBit(n)) == 0;
    }

    /**
     * Given an integer N and a number of right shifts to perform, rotate the bits in the given number clockwise by that amount.
     * @param n the number to shift.
     * @param shift the amount of bits to rotate clockwise.
     * @return the integer resulting from the right rotation of the given number by the given amount of bits.
     */
    public static int rightRotateShiftBits(int n, int shift){
        //right shift >> would protect the sign so the MSB is left untouched, we used >>> to do a bitwise operation
        //however << and <<< would have same meaning, therefore there is no <<< operation
        //for negative numbers Java uses 2's complement so for a negative number UNSET bits are 1s and not 0s
        //if we pass a negative int in input this will NOT consider it as MSB = 1, rest = 0s for unset bit then
        //therefore the result of the shift will still be negative
        return n >>> shift | n << Integer.SIZE - shift;
    }

    /**
     * Given an integer N and a number of left shifts to perform, rotate the bits in the given number counterclockwise by that amount.
     * @param n the number to shift.
     * @param shift the amount of bits to rotate counterclockwise.
     * @return the integer resulting from the left rotation of the given number by the given amount of bits.
     */
    public static int leftRotateShiftBits(int n, int shift){
        //right shift >> would protect the sign so the MSB is left untouched, we used >>> to do a bitwise operation
        //however << and <<< would have same meaning, therefore there is no <<< operation
        //for negative numbers Java uses 2's complement so for a negative number UNSET bits are 1s and not 0s
        //if we pass a negative int in input this will NOT consider it as MSB = 1, rest = 0s for unset bit then
        //therefore the result of the shift will still be negative
        return n << shift | n >>> Integer.SIZE - shift;
    }

    /**
     * Given two numbers find if they respect the Gray distance, that is both numbers differ by just one bit.
     * @param n first number.
     * @param m second number.
     * @return true if the binary representation of these numbers differ by just one bit.
     */
    public static boolean isGrayDistance(long n, long m){
        //necessary since we will go into weird situations where the manipulations make same number become different
        //for example if we go into negative territory as Java does not unsigned type
        if(n == m){
            return false;
        }
        /*
        Approach 1:
        x = XOR the numbers to get only the different bits. If they are Gray, there must be only one different bit.
        y = getLowestSetBit(x), to get the lowest set bit in our x: magic formula is n & ~(n - 1)
        x - y == 0, if there was only one set bit x and y must be equal therefore the difference must be zero

        Approach 2:
        x = XOR the numbers to get only the different bits. If they are Gray, there must be only one different bit.
        y = x - 1, if there was only one set bit now we removed it from that place and therefore x and y don't align anymore on that bit
        x & y == 0, of there was only one set bit, x and y don't align therefore the bitwise AND wil give all zeros
         */
        long c = n ^ m;
        /*long d = getLowestSetBit(c);
        return c - d == 0;*/
        return (c & (c-1)) == 0;
    }

    /**
     * Given an array of positive numbers without duplicates in the range 1..N and size N-2, find the two missing numbers.
     * @param numbers the given numbers.
     * @return the pair of missing numbers.
     */
    public static Pair<Integer, Integer> findTwoMissingNumbers(int... numbers){
        Pair<Integer, Integer> missing = new Pair<>();

        if(numbers == null){
            return missing;
        }

        /*
        XOR of all elements in range 1..N with all elements in array gives Z, which is XOR of missing numbers X,Y
        Since we have no duplicates and missing numbers are in range 1..N, we know X and Y cannot be equal,
        this means X will have a bit set in a place that Y hasn't otherwise XOR would be 0 since it sets a 1 in
        every place where the two bits are different
        We can get a set bit in Z with the magic formula z & ~(z - 1)
        We can then divide the array in two sets of elements, those who have that bit set and those who don't
        We XOR all those elements together and also with all elements in range 1..N that also have the same bit set or not
        The result of the two sets of XORs are X and Y

        Example:

        4,2,3 we are missing 1,5: 001, 101

        xor of all numbers 1..5 is: 1
        xor of all elements in the array is: 5
        z is: 4

        since x,y cannot be the same number, they have for sure at least one different bit
        we pick rightmost set bit in the xor: 4

        a = xor of all numbers in range 1..5 with that bit set is: 0
        b = xor of all numbers in range 1..5 with that bit NOT set is: 1

        c = xor of all elements in array with that bit set is: 1
        d = xor of all elements in array with that bit NOT set is: 4

        x = a ^ c = 1
        y = b ^ d = 5

         */

        //xor all numbers in range 1..N
        int z = 0;
        for(int i = 1; i <= numbers.length + 2; i++){
            z ^= i;
        }

        //together with all values in our array
        for(int i = 0; i < numbers.length; i++){
            z ^= numbers[i];
        }

        //pick any set bit in the xor, we get the rightmost one with the magic formula
        int setBit = z & ~(z - 1);

        //now xor together all items in range 1..N that have the bit set (X) and do same for those who don't
        //have that bit set (Y)
        int x = 0, y = 0;
        for(int i = 1; i <= numbers.length + 2; i++){
            if((i & setBit) == 0){
                x ^= i;
            }
            else{
                y ^= i;
            }
        }

        //XOR X with all elements in the array that have the bit set and XOR Y with all elements in the array who don't
        for(int i = 0; i < numbers.length; i++){
            if((numbers[i] & setBit) == 0){
                x ^= numbers[i];
            }
            else{
                y ^= numbers[i];
            }
        }

        //now we have our X and Y missing numbers, for practicality we order them so the smallest is always first in the result
        if(x > y){
            int tmp = x;
            x = y;
            y = tmp;
        }

        missing.setFirst(x);
        missing.setSecond(y);

        return missing;
    }

    /**
     * Calculates GCD for the given numbers.
     * @param a the first number.
     * @param b the second number.
     * @return the GCD of both numbers.
     */
    public static int gcd(int a, int b){

        return gcd(a, b, 1);

    }

    private static int gcd(int a, int b, int res){

        if(a == b) return res * a;

        if(a % 2 == 0 && b % 2 == 0) return gcd(a >> 1, b >> 1, res << 1);

        if(a % 2 == 0) return gcd(a >> 1, b , res);

        if(b % 2 == 0) return gcd(a, b >> 1, res);

        if(a > b) return gcd(a - b, b, res);

        return gcd(a, b - a, res);
    }

    /**
     * Calculates the LCM for two given numbers.
     * @param a the first number.
     * @param b the second number.
     * @return the LCM of both numbers.
     */
    public static int lcm(int a, int b){
        return (a * b) / gcd(a, b);
    }

    /**
     * Increment the given number by 1 without using sum operator.
     * @param n the given number.
     * @return n + 1.
     */
    public static int increment1(int n){
        //numbers are stored in 2's complement. To obtain it, bits are inverted then 1 is added
        //we can therefore get n+1 by flipping all bits first, then flipping the sign
        return -(~n);
    }

    /**
     * Sum two numbers without using sum operator.
     * @param a the first number.
     * @param b the second number.
     * @return a + b.
     */
    public static int sum(int a, int b){
        int carry = 0;
        int sum = 0;
        int lsb1mask = 1;
        int position = 0;

        //sum all bits until we can, then copy rest of longer number
        while(a != 0 || b != 0){
            //get lsb for a and b
            int alsb = a & lsb1mask;
            int blsb = b & lsb1mask;

            //sum = 1 only if:
            //lsb a + lsb b = 0 AND carry = 1
            //lsb a AND lsb b = 0 AND carry = 1
            //we use XOR to get the result we want
            int res = alsb ^ blsb ^ carry;

            //this bit goes into this place
            res = res << position;

            //set this bit in the final sum
            sum |= res;

            //carry for next position is 1 if:
            //lsb a & lsb b = 1
            //lsb a & carry = 1
            //lsb b & carry = 1
            //basically if there were at least 2 ones among lsb a, lsb b, carry
            carry = (alsb & blsb) | (alsb & carry) | (blsb & carry);

            //increment position, we can't use sum operator
            position = -(~position);

            //throw away this bit from both and do NOT preserve sign
            a = a >>> 1;
            b = b >>> 1;
        }

        //set the carry (if any remaining) unless we are overriding MSB
        if(carry != 0 && position < 32){
            int res = carry << position;
            sum |= res;
        }

        return sum;
    }

    /**
     * Given a positive integer n, return for each integer in range 0..N both inclusive, the number of bits set to
     * 1 in each value.
     * @param n the input number.
     * @return an array where at each position we have the number of bits set to 1 for the integer corresponding to that index.
     */
    public static int[] countOnes(int n){
        if(n < 0){
            return null;
        }

        /*
        We could for each integer in range 0..N consider its binary representation and
        pick off all bits set to 1 counting them
        This would make us do 32 operations for each number. Being 32 a constant we'd have linear time
        but performance is still impacted.

        We can however reuse information we stored earlier (especially in this case it's part of our answer anyway)
        Drawing the sequence for 0..8 gives us:
        0: 0000
        1: 0001
        2: 0010
        3: 0011
        4: 0100
        5: 0101
        6: 0110
        7: 0111
        8: 1000

        And we notice that N and N*2 have exactly the same amount of bits set, just shifted left one position, example
        3 and 6
        2, 4 and 8
        What is left out is odd numbers like 5 and 7. But in that case, it's just about setting the lsb to 1 from the
        previous number, example
        5 = 4 + 1
        7 = 6 + 1
        so we can simply start from N/2, shift it up one position AND check if we should set the lsb to 1 in this new number
        If we know how many bits are set in N/2, we skip all of this process and just reuse that value and
        add one if the lsb should be 1.
        This is also equal to saying number of bits set in N/2 + N mod 2 as that will be always 0 for even numbers and
        always 1 for odd numbers

        repeat this process for all numbers in our range and we have the solution
         */
        int[] out = new int[n + 1];

        for(int i = 0; i < out.length; i++){
            out[i] = out[i / 2] + (i & 1); //or + i % 2
        }

        return out;
    }

    /**
     * Given an array of unique integers in range 0..N with only one missing value, find the missing value.
     * @param numbers the input numbers.
     * @return the missing value.
     */
    public static int findMissingNumber(int... numbers){
        if(numbers == null){
            return -1;
        }

        int res = numbers.length;

        //if we XOR all values with all indices in the array, matching numbers would cancel out
        //the only missing number (index) would be left instead
        //we initialize to numbers.length as that is not a valid index, but is a valid number in range 0..N
        //so we don't exclude it
        for(int i = 0; i < numbers.length; i++){
            res ^= i ^ numbers[i];
        }

        return res;
    }

    /**
     * Given an integer representing a 32 bit sequence, reverse it.
     * @param n the integer representing the 32 bit sequence.
     * @return the reversed 32 bit sequence.
     */
    public static int reverseBits(int n){
        //take half of the bits from MSB to mid portion
        //take half of the bits from mid to LSB portion
        //swap them
        //repeat the process with always smaller masks and portions
        //mask is always 32 bit in size

        //initial swap, throw away 16 LSB and 16 MSB, combine them together
        //now we have the two halves reversed
        n = n >>> 16 | n << 16;

        //mask for left portion:  1111 1111 0000 0000 1111 1111 0000 0000
        //mask for right portion: 0000 0000 1111 1111 0000 0000 1111 1111
        //then shift by half of previous size (8 bit)
        n = (n & 0xff00ff00) >>> 8 | (n & 0x00ff00ff) << 8;

        //mask for left portion:  1111 0000 1111 0000 1111 0000 1111 0000
        //mask for right portion: 0000 1111 0000 1111 0000 1111 0000 1111
        //then shift by half of previous size (4 bit)
        n = (n & 0xf0f0f0f0) >>> 4 | (n & 0x0f0f0f0f) << 4;

        //mask for left portion:  1100 1100 1100 1100 1100 1100 1100 1100
        //mask for right portion: 0011 0011 0011 0011 0011 0011 0011 0011
        //then shift by half of previous size (2 bit)
        n = (n & 0xcccccccc) >>> 2 | (n & 0x33333333) << 2;

        //mask for left portion:  1010 1010 1010 1010 1010 1010 1010 1010
        //mask for right portion: 0101 0101 0101 0101 0101 0101 0101 0101
        //then shift by half of previous size (1 bit)
        n = (n & 0xaaaaaaaa) >>> 1 | (n & 0x55555555) << 1;

        //now all the bits have been moved around in the reverse place
        return n;
    }
}

BitUtilsJTests.java

package com.blogspot.groglogs.test.bitutils;

import com.blogspot.groglogs.bitutils.BitUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class BitUtilsJTests {

    long in, out;

    @Test
    public void getLowestSetBit() {

        in = 0;
        out = 0;

        assertEquals("getLowestSetBit 0 expected 0", out, BitUtils.getLowestSetBit(in));

        in = 1;
        out = 1;

        assertEquals("getLowestSetBit 1 expected 1", out, BitUtils.getLowestSetBit(in));

        in = 2;
        out = 2;

        assertEquals("getLowestSetBit 10 expected 2", out, BitUtils.getLowestSetBit(in));

        in = 3;
        out = 1;

        assertEquals("getLowestSetBit 11 expected 1", out, BitUtils.getLowestSetBit(in));

        in = 4;
        out = 4;

        assertEquals("getLowestSetBit 100 expected 4", out, BitUtils.getLowestSetBit(in));
    }

    @Test
    public void getLowestSetBitPosition() {

        in = 0;
        out = -1;

        assertEquals("getLowestSetBitPosition 0 expected -1", out, BitUtils.getLowestSetBitPosition(in));

        in = 1;
        out = 0;

        assertEquals("getLowestSetBitPosition 1 expected 0", out, BitUtils.getLowestSetBitPosition(in));

        in = 2;
        out = 1;

        assertEquals("getLowestSetBitPosition 10 expected 1", out, BitUtils.getLowestSetBitPosition(in));

        in = 3;
        out = 0;

        assertEquals("getLowestSetBitPosition 11 expected 0", out, BitUtils.getLowestSetBitPosition(in));

        in = 4;
        out = 3;

        assertEquals("getLowestSetBitPosition 100 expected 3", out, BitUtils.getLowestSetBitPosition(in));
    }

    @Test
    public void rightPropagateLowestSetBit() {

        in = 0;
        out = 0;

        assertEquals("rightPropagateLowestSetBit 0 expected 0", out, BitUtils.rightPropagateLowestSetBit(in));

        in = 1;
        out = 1;

        assertEquals("rightPropagateLowestSetBit 1 expected 1", out, BitUtils.rightPropagateLowestSetBit(in));

        in = 2;
        out = 3;

        assertEquals("rightPropagateLowestSetBit 10 expected 3", out, BitUtils.rightPropagateLowestSetBit(in));

        in = 3;
        out = 3;

        assertEquals("rightPropagateLowestSetBit 11 expected 3", out, BitUtils.rightPropagateLowestSetBit(in));

        in = 4;
        out = 7;

        assertEquals("rightPropagateLowestSetBit 100 expected 7", out, BitUtils.rightPropagateLowestSetBit(in));

        in = 80;
        out = 95;

        assertEquals("rightPropagateLowestSetBit 01010000 expected 95", out, BitUtils.rightPropagateLowestSetBit(in));
    }

    @Test
    public void moduloPower2() {
        long mod;

        in = 0;
        mod = 64;
        out = 0;

        assertEquals("moduloPower2 0 mod 64 expected 0", out, BitUtils.moduloPower2(in, mod));

        in = 3;
        mod = 64;
        out = 3;

        assertEquals("moduloPower2 3 mod 64 expected 3", out, BitUtils.moduloPower2(in, mod));

        in = 64;
        mod = 64;
        out = 0;

        assertEquals("moduloPower2 64 mod 64 expected 0", out, BitUtils.moduloPower2(in, mod));

        in = 128;
        mod = 64;
        out = 0;

        assertEquals("moduloPower2 128 mod 64 expected 0", out, BitUtils.moduloPower2(in, mod));

        in = 77;
        mod = 64;
        out = 13;

        assertEquals("moduloPower2 77 mod 64 expected 13", out, BitUtils.moduloPower2(in, mod));

        in = 129;
        mod = 64;
        out = 1;

        assertEquals("moduloPower2 129 mod 64 expected 1", out, BitUtils.moduloPower2(in, mod));
    }

    @Test
    public void isPower2() {

        in = 0;

        assertEquals("isPower2 0 expected false", false, BitUtils.isPower2(in));

        in = 1;

        assertEquals("isPower2 1 expected true", true, BitUtils.isPower2(in));

        in = 2;

        assertEquals("isPower2 2 expected true", true, BitUtils.isPower2(in));

        in = 3;

        assertEquals("isPower2 3 expected false", false, BitUtils.isPower2(in));

        in = 4;

        assertEquals("isPower2 4 expected true", true, BitUtils.isPower2(in));

        in = 64;

        assertEquals("isPower2 64 expected true", true, BitUtils.isPower2(in));

        in = 129;

        assertEquals("isPower2 129 expected false", false, BitUtils.isPower2(in));
    }

    @Test
    public void rightRotateShiftBits() {
        int number = 3, out = 3;
        int shift = 0;
        assertEquals("0 shift is same number", out, BitUtils.rightRotateShiftBits(number, shift));

        number = 3; //00000000000000000000000000000011
        out = -1073741824; //11000000000000000000000000000000
        shift = 2;
        assertEquals("right shift positive number which makes it negative", out, BitUtils.rightRotateShiftBits(number, shift));

        number = 3; //00000000000000000000000000000011
        out = 1610612736; //01100000000000000000000000000000
        shift = 3;
        assertEquals("right shift positive number", out, BitUtils.rightRotateShiftBits(number, shift));

        //sample Integer.toBinaryString(number)
        number = -3; //binary would be 10000000000000000000000000000011 but it actually is 11111111111111111111111111111101
        //unsigned would be 01110000000000000000000000000000 = 1879048192
        //but since we bitwise shift on the negative representation we get 10111111111111111111111111111111
        out = -1073741825;
        shift = 3;
        assertEquals("right shift negative number", out, BitUtils.rightRotateShiftBits(number, shift));
    }

    @Test
    public void leftRotateShiftBits() {
        int number = 3, out = 3;
        int shift = 0;
        assertEquals("0 shift is same number", out, BitUtils.leftRotateShiftBits(number, shift));

        number = 3; //00000000000000000000000000000011
        out = 24; //00000000000000000000000000011000
        shift = 3;
        assertEquals("left shift positive number", out, BitUtils.leftRotateShiftBits(number, shift));

        //-3 >>> 3 = 536870911

        //sample Integer.toBinaryString(number)
        number = -3; //binary would be 10000000000000000000000000000011 but it actually is 11111111111111111111111111111101
        //unsigned would be 00000000000000000000000000011100 = 28
        //but since we bitwise shift on the negative representation we get 11111111111111111111111111101111
        out = -17;
        shift = 3;
        assertEquals("left shift negative number", out, BitUtils.leftRotateShiftBits(number, shift));
    }

    @Test
    public void isGrayDistance(){
        in = 0;
        out = 0;
        assertFalse("0,0 are not Gray", BitUtils.isGrayDistance(in, out));

        in = 1;
        out = 1;
        assertFalse("1,1 are not Gray", BitUtils.isGrayDistance(in, out));

        in = 2;
        out = 2;
        assertFalse("2,2 are not Gray", BitUtils.isGrayDistance(in, out));

        in = 0;
        out = 1;
        assertTrue("0,1 are Gray", BitUtils.isGrayDistance(in, out));

        in = 0;//00
        out = 2;//10
        assertTrue("0,2 are Gray", BitUtils.isGrayDistance(in, out));

        in = 1;//01
        out = 2;//10
        assertFalse("1,2 are not Gray", BitUtils.isGrayDistance(in, out));

        in = 1;//01
        out = 3;//11
        assertTrue("1,3 are Gray", BitUtils.isGrayDistance(in, out));

        in = 7;//111
        out = 5;//101
        assertTrue("7,5 are Gray", BitUtils.isGrayDistance(in, out));

        in = 15;//1111
        out = 9;//1001
        assertFalse("15,9 are not Gray", BitUtils.isGrayDistance(in, out));
    }
}

CountOnesJTests.java

package com.blogspot.groglogs.test.bitutils;

import com.blogspot.groglogs.bitutils.BitUtils;
import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;

public class CountOnesJTests {
    int n;
    int[] out, expected;

    @Test
    public void negative(){
        n = -1;
        expected = null;
        out = BitUtils.countOnes(n);
        assertArrayEquals("-1", expected, out);
    }

    @Test
    public void zero(){
        n = 0;
        expected = new int[]{0};
        out = BitUtils.countOnes(n);
        assertArrayEquals("0", expected, out);
    }

    @Test
    public void one(){
        n = 1;
        expected = new int[]{0,1};
        out = BitUtils.countOnes(n);
        assertArrayEquals("1", expected, out);
    }

    @Test
    public void two(){
        n = 2;
        expected = new int[]{0,1,1};
        out = BitUtils.countOnes(n);
        assertArrayEquals("2", expected, out);
    }

    @Test
    public void three(){
        n = 3;
        expected = new int[]{0,1,1,2};
        out = BitUtils.countOnes(n);
        assertArrayEquals("3", expected, out);
    }

    @Test
    public void sample(){
        n = 5;
        expected = new int[]{0,1,1,2,1,2};
        out = BitUtils.countOnes(n);
        assertArrayEquals("5", expected, out);
    }
}

FindMissingNumberJTests.java

package com.blogspot.groglogs.test.bitutils;

import com.blogspot.groglogs.bitutils.BitUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class FindMissingNumberJTests {
    int[] numbers;
    int expected;

    @Test
    public void nullArray(){
        numbers = null;
        expected = -1;
        assertEquals("null", expected, BitUtils.findMissingNumber(numbers));
    }

    @Test
    public void missingZero(){
        numbers = new int[]{1};
        expected = 0;
        assertEquals("1", expected, BitUtils.findMissingNumber(numbers));

        numbers = new int[]{1,2};
        expected = 0;
        assertEquals("1,2", expected, BitUtils.findMissingNumber(numbers));

        numbers = new int[]{2,1};
        expected = 0;
        assertEquals("2,1", expected, BitUtils.findMissingNumber(numbers));
    }

    @Test
    public void missingOne(){
        numbers = new int[]{0};
        expected = 1;
        assertEquals("0", expected, BitUtils.findMissingNumber(numbers));

        numbers = new int[]{0,2};
        expected = 1;
        assertEquals("0,2", expected, BitUtils.findMissingNumber(numbers));

        numbers = new int[]{2,0};
        expected = 1;
        assertEquals("2,0", expected, BitUtils.findMissingNumber(numbers));
    }

    @Test
    public void missingTwo(){
        numbers = new int[]{0,1};
        expected = 2;
        assertEquals("0,1", expected, BitUtils.findMissingNumber(numbers));

        numbers = new int[]{1,0};
        expected = 2;
        assertEquals("1,0", expected, BitUtils.findMissingNumber(numbers));

        numbers = new int[]{0,1,3};
        expected = 2;
        assertEquals("0,1,3", expected, BitUtils.findMissingNumber(numbers));
    }
}

GCDJTests.java

package com.blogspot.groglogs.test.bitutils;

import com.blogspot.groglogs.bitutils.BitUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class GCDJTests {

    int a, b, gcd;

    @Test
    public void zero() {
        a = 0;
        b = 0;
        gcd = 0;
        assertEquals("zero", gcd, BitUtils.gcd(a, b));
    }

    @Test
    public void primes() {
        a = 7;
        b = 13;
        gcd = 1;
        assertEquals("7,13", gcd, BitUtils.gcd(a, b));
    }

    @Test
    public void multiple() {
        a = 9;
        b = 3;
        gcd = 3;
        assertEquals("3,9", gcd, BitUtils.gcd(a, b));
    }

    @Test
    public void sample() {
        a = 15;
        b = 70;
        gcd = 5;
        assertEquals("15,70", gcd, BitUtils.gcd(a, b));
    }
}

Increment1JTests.java

package com.blogspot.groglogs.test.bitutils;

import com.blogspot.groglogs.bitutils.BitUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class Increment1JTests {

    @Test
    public void zero(){
        assertEquals("0", 1, BitUtils.increment1(0));
    }

    @Test
    public void negative(){
        assertEquals("-1", 0, BitUtils.increment1(-1));

        assertEquals("-2", -1, BitUtils.increment1(-2));
    }

    @Test
    public void positive(){
        assertEquals("1", 2, BitUtils.increment1(1));
    }
}

LCMJTests.java

package com.blogspot.groglogs.test.bitutils;

import com.blogspot.groglogs.bitutils.BitUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class LCMJTests {

    int a, b, lcm;

    @Test(expected = ArithmeticException.class)
    public void zero() {
        a = 0;
        b = 0;
        BitUtils.lcm(a, b);
    }

    @Test
    public void primes() {
        a = 7;
        b = 13;
        lcm = a * b;
        assertEquals("7,13", lcm, BitUtils.lcm(a, b));
    }

    @Test
    public void multiple() {
        a = 9;
        b = 3;
        lcm = a;
        assertEquals("3,9", lcm, BitUtils.lcm(a, b));
    }

    @Test
    public void sample() {
        a = 15;
        b = 70;
        lcm = 210;
        assertEquals("15,70", lcm, BitUtils.lcm(a, b));
    }
}

MissingTwoNumbersInArrayJTests.java

package com.blogspot.groglogs.test.bitutils;

import com.blogspot.groglogs.bitutils.BitUtils;
import com.blogspot.groglogs.structures.Pair;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class MissingTwoNumbersInArrayJTests {

    int[] numbers;
    Pair<Integer, Integer> expected;

    @Test
    public void nullArray() {
        numbers = null;
        expected = new Pair<>();
        assertEquals("null array", expected, BitUtils.findTwoMissingNumbers(numbers));
    }

    @Test
    public void emptyArray() {
        numbers = new int[]{};
        expected = new Pair<>(1, 2);
        assertEquals("empty array", expected, BitUtils.findTwoMissingNumbers(numbers));
    }

    @Test
    public void oneElement() {
        numbers = new int[]{1};
        expected = new Pair<>(2, 3);
        assertEquals("1", expected, BitUtils.findTwoMissingNumbers(numbers));

        numbers = new int[]{2};
        expected = new Pair<>(1, 3);
        assertEquals("2", expected, BitUtils.findTwoMissingNumbers(numbers));

        numbers = new int[]{3};
        expected = new Pair<>(1, 2);
        assertEquals("3", expected, BitUtils.findTwoMissingNumbers(numbers));
    }

    @Test
    public void sample() {
        numbers = new int[]{4, 2, 3};
        expected = new Pair<>(1, 5);
        assertEquals("4, 2, 3", expected, BitUtils.findTwoMissingNumbers(numbers));

        numbers = new int[]{1, 4, 2, 3};
        expected = new Pair<>(5, 6);
        assertEquals("1, 4, 2, 3", expected, BitUtils.findTwoMissingNumbers(numbers));

        numbers = new int[]{4, 3, 5, 6};
        expected = new Pair<>(1, 2);
        assertEquals("4, 3, 5, 6", expected, BitUtils.findTwoMissingNumbers(numbers));
    }
}

Pair.java

package com.blogspot.groglogs.structures;

import java.util.Objects;

/**
 * Defines a Pair of objects.
 * @param <T> type of the first object.
 * @param <E> type of the second object.
 */
public class Pair<T, E> {

    private T first;
    private E second;

    public Pair(){
        this.first = null;
        this.second = null;
    }

    public Pair(T first, E second){
        this.first = first;
        this.second = second;
    }

    public T getFirst(){
        return this.first;
    }

    public E getSecond(){
        return this.second;
    }

    public void setFirst(T first){
        this.first = first;
    }

    public void setSecond(E second){
        this.second = second;
    }

    @Override
    public int hashCode() {
        return Objects.hash(this.first, this.second);
    }

    @Override
    public boolean equals(Object o) {
        if(this == o){
            return true;
        }

        if(!(o instanceof Pair)){
            return false;
        }

        //the other pair could be typed differently, we accept it since the equals later will factor these types in
        Pair<?,?> other = (Pair<?,?>)o;

        //Objects.equals logic is: this.first == null ? other.first == null : this.first.equals(other.first)
        //which guarantees null safety AND factors in the typechecking by using the relevant equals logic of our field types
        return Objects.equals(this.first, other.first) && Objects.equals(this.second, other.second);
    }
}

SumJTests.java

package com.blogspot.groglogs.test.bitutils;

import com.blogspot.groglogs.bitutils.BitUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class SumJTests {
    int a, b, expected;

    @Test
    public void zero(){
        a = 0;
        b = 0;
        expected = 0;
        assertEquals("0", expected, BitUtils.sum(a,b));

        a = 1;
        b = -1;
        expected = 0;
        assertEquals("1,-1", expected, BitUtils.sum(a,b));
    }

    @Test
    public void positive(){
        a = 1;
        b = 0;
        expected = 1;
        assertEquals("0,1", expected, BitUtils.sum(a,b));

        a = 1;
        b = 2;
        expected = 3;
        assertEquals("1,2", expected, BitUtils.sum(a,b));

        a = 2;
        b = 3;
        expected = 5;
        assertEquals("2,3", expected, BitUtils.sum(a,b));
    }

    @Test
    public void negative(){
        a = -1;
        b = 0;
        expected = -1;
        assertEquals("0,-1", expected, BitUtils.sum(a,b));

        a = -1;
        b = -2;
        expected = -3;
        assertEquals("-1,-2", expected, BitUtils.sum(a,b));

        a = -2;
        b = -3;
        expected = -5;
        assertEquals("-2,-3", expected, BitUtils.sum(a,b));
    }

    @Test
    public void mix(){
        a = -1;
        b = 2;
        expected = 1;
        assertEquals("-1,2", expected, BitUtils.sum(a,b));
    }
}

Full description at:

• https://groglogs.blogspot.com/2021/07/java-reverse-integer.html
• https://groglogs.blogspot.com/2021/07/java-find-missing-integer-in-array-of.html
• https://groglogs.blogspot.com/2021/07/java-count-number-of-bits-set-to-1.html
• https://groglogs.blogspot.com/2021/07/java-sum-two-integers-without-sum.html
• https://groglogs.blogspot.com/2021/07/java-increment-number-without-using-sum.html
• https://groglogs.blogspot.com/2021/06/java-find-two-missing-numbers-in-array.html
• https://groglogs.blogspot.com/2021/06/java-test-whether-two-numbers-are-at.html
• https://groglogs.blogspot.com/2021/06/java-circular-right-and-left-bit-shifts.html
• http://groglogs.blogspot.ch/2017/10/java-find-lowest-set-bit-in-number.html
• http://groglogs.blogspot.ch/2017/10/java-right-propagate-lowest-set-bit-in.html
• http://groglogs.blogspot.ch/2017/10/java-calculate-modulus-of-number-and.html
• http://groglogs.blogspot.ch/2017/10/java-test-if-number-is-power-of-two.html