Skip to main content

Bit Manipulation

  • Understanding bit manipulation
  • Important concepts
  • Solved problems are presented in alphabetical order

Important Concepts

Binary Addition/Multiplication/Division

  • Similar to decimal addition/multiplication/division

Binary Subtraction

1's and 2's Complement

  • 1's complement means changing 1s to 0s and 0s to 1s.
    • 1's complement of 11101110: 00010001
  • 2's complement means adding 1 to 1's complement
    • 2's complement of 11101110: 0001+1=00100001 + 1 = 0010
Binary Subtraction Using 1's Complement
  • We can subtract B from A using 1's Complement using the following steps:
    1. Both A and B must have same number of bits to start with
      • 0s can be added in the beginning to make the number of bits equal
    2. Find 1's complement of B
    3. Add A to 1's complement of B
    4. There are two possibilities following the addtion in the step above.
      • #1: We'll have 1 extra bit in addition to the total number of bits in A or B.
      • #2: We'll have the same number of bits as in A or B
    5. In the case of one additional bit, we do the following
      • First, separate the most significant bit (MSB) from the rest of the number
      • MSB is generally the bit farthest to the left of a binary number
      • Second, add the MSB to the rest of the number to get our result
    6. In the case of the same number of bits, we do the following
      • First, take 1's complement of the number
      • Second, add a negative sign in front of it to get our result
  • Example 1: A=1000A = 1000 and B=1110B = 1110
    1. 1's complement of B: 00010001
    2. 1000+0001=10011000 + 0001 = 1001
    3. 1's complement of 10011001 = 01100110
    4. AB=0110A - B = -0110
  • Example 2: A=1110A = 1110 and B=1000B = 1000
    1. 1's complement of B: 01110111
    2. 1110+0111=101011110 + 0111 = 10101
    3. We have 11 (MSB) and 01010101
    4. 0101+0001=01100101 + 0001 = 0110
    5. AB=0110A - B = 0110
Binary Subtraction Using 2's Complement
  • We can subtract B from A using 2's Complement using the following steps:
    1. Both A and B must have same number of bits to start with
      • 0s can be added in the beginning to make the number of bits equal
    2. Find 2's complement of B
    3. Add A to 2's complement of B
    4. There are two possibilities following the addtion in the step above.
      • #1: We'll have 1 extra bit in addition to the total number of bits in A or B.
      • #2: We'll have the same number of bits as in A or B
    5. In the case of one additional bit, we do the following
      • Separate the most significant bit (MSB) from the rest of the number
      • MSB is generally the bit farthest to the left of a binary number
      • The rest of the number (without the MSB) is our result
    6. In the case of the same number of bits, we do the following
      • First, take 2's complement of the number
      • Second, add a negative sign in front of it to get our result
  • Example 1: A=1000A = 1000 and B=1110B = 1110
    1. 2's complement of B: 00100010
    2. 1000+0010=10101000 + 0010 = 1010
    3. 2's complement of 10101010 = 01100110
    4. AB=0110A - B = -0110
  • Example 2: A=1110A = 1110 and B=1000B = 1000
    1. 2's complement of B: 10001000
    2. 1110+1000=101101110 + 1000 = 10110
    3. We have 11 (MSB) and 01100110
    4. AB=0110A - B = 0110

Bitwise Operators

OperatorSymbolDescription
AND&0 & 1 or 0 & 0 is 0; 1 & 1 is 1
OR|0 | 1 or 1 | 1 is 1; 0 | 0 is 0
XOR^0^0 or 1^1 is 0; 0^1 is 1 (i.e., 1 for different bits, 0 for same bits)
NOT~~0 is a sequence of 1s and ~1 of 0s (i.e., 1 becomes 0 and 0 becomes 1)

Bitwise Shift Operators

OperatorDescription
<<Left shift: bits are shifted to the left, and empty spaces are filled by 0s
Example: 11111<<3=1100011111 << 3 = 11000
>>Right shift: bits are shifted to the right, empty spaces are filled by 0s
Example: 11111>>3=0001111111 >> 3 = 00011

Truth Tables

  • 0: False
  • 1: True

Bitwise OR

Output0111
P0011
Q0101

Bitwise XOR (Exclusive OR)

Output0110
P0011
Q0101

Bitwise AND

Output0001
P0011
Q0101

Frequently Encountered Results

ResultDescription
OR
A | A = ASame operand on either side of the operator
Example 1 (A = 0): 0 | 0 = 0
Example 2 (A = 1): 1 | 1 = 1
A | 0s = AA | FALSE is always A
Example 1 (A = 0): 0 | 0 = 0
Example 2 (A = 1): 1 | 0 = 1
A | 1s = 1sA | TRUE is always TRUE
Example 1 (A = 0): 0 | 1 = 1
Example 2 (A = 1): 1 | 1 = 1
XOR
A ^ A = 0If both operands are the same, XOR always yields FALSE
Example 1 (A = 0): 0 ^ 0 = 0
Example 2 (A = 1): 1 ^ 1 = 0
A ^ 0s = AOne operand is A, while the other is FALSE; so, XOR always yields A
Example 1 (A = 0): 0 ^ 0 = 0
Example 2 (A = 1): 1 ^ 0 = 1
A ^ 1s = ~AOne operand is A, while the other is TRUE; so, XOR NEVER yields A
Example 1 (A = 0): 0 ^ 1 = 1
Example 2 (A = 1): 1 ^ 1 = 0
AND
A & A = ASame operand on either side of the operator
Example 1 (A = 0): 0 & 0 = 0
Example 2 (A = 1): 1 & 1 = 1
A & 0s = 0One operand is FALSE; so, AND always yields FALSE
Example 1 (A = 0): 0 & 0 = 0
Example 2 (A = 1): 1 & 0 = 0
A & 1s = AOne operand is A, while the other is TRUE; so, AND always yields A
Example 1 (A = 0): 0 & 1 = 0
Example 2 (A = 1): 1 & 1 = 1
Add Binary

↗ See LeetCode Problem #67

import java.math.BigInteger;public class Solution {    static String addBinary(String a, String b) {        //  Approach 1: Might not be acceptable to the interviwer//        return Integer.toBinaryString(//                Integer.parseInt(a,2) + Integer.parseInt(b, 2));        //  Approach 2: XOR a and b (to get respone without carry)        //      AND a and b and then left shift by 1 (<< 1)        //          (to get respone with carry)        //      Set a = the respone without carry        //      Set b = the respone with carry        //      Continue while carry != 0        BigInteger bigA = new BigInteger(a, 2);        BigInteger bigB = new BigInteger(b, 2);        BigInteger bigZero = new BigInteger("0", 2);        BigInteger temp;        BigInteger carry;        while (bigB.compareTo(bigZero) != 0) {            temp = bigA.xor(bigB);            carry = bigA.and(bigB).shiftLeft(1);            //  Update bigA            bigA = temp;            //  Update bigB            bigB = carry;        }        return bigA.toString(2);    }    public static void main(String[] args) {        // Example 1:        String a1 = "11";        String b1 = "1";        //  O/P: "100"        // Example 2:         String a2 = "1010";         String b2 = "1011";        //  O/P: "10101"        System.out.println(addBinary(a1, b1));        System.out.println(addBinary(a2, b2));    }}
Counting Bits

↗ See LeetCode Problem #338

import java.util.Arrays;public class Solution {    static int[] countBits(int n) {        int[] ans = new int[n + 1];        for (int i = 1; i <= n; ++i) {            //  i / 2 is i >> 1 (bit right shift operation)            //  i % 2 is i & 1            ans[i] = ans[i >> 1] + (i & 1);        }        return ans;    }    public static void main(String[] args) {        // Example 1:        int n1 = 2;        //  O/P: [0,1,1]        // Example 2:        int n2 = 5;        //  O/P: [0,1,1,2,1,2]        // Example 3:        int n3 = 55;        System.out.println(Arrays.toString(countBits(n1)));        System.out.println(Arrays.toString(countBits(n2)));        System.out.println(Arrays.toString(countBits(n3)));    }}
Find the Duplicate Number

↗ See LeetCode Problem #287

// Will be updated soon
Missing Number

↗ See LeetCode Problem #268

public class Solution {    static int missingNumber(int[] nums) {        //  nums.length will always be in the given array        //      but it won't appear as an index in the for loop        int missing = nums.length;        for (int i = 0; i < nums.length; i++) {            missing ^= nums[i] ^ i;        }        return missing;    }    public static void main(String[] args) {        // Example 1:        int[] nums1 = {3, 0, 1};        //  O/P: 2        // Example 2:        int[] nums2 = {0, 1};        //  O/P: 2        // Example 3:        int[] nums3 = {9, 6, 4, 2, 3, 5, 7, 0, 1};        //  O/P: 8        // Example 4:        int[] nums4 = {2, 0, 3};        //  O/P: 2        // 3^2^0^0^1^3^2        System.out.println("Example 1: " + missingNumber(nums1));        System.out.println("Example 2: " + missingNumber(nums2));        System.out.println("Example 3: " + missingNumber(nums3));        System.out.println("Example 4: " + missingNumber(nums4));    } }
Number of 1 Bits

↗ See LeetCode Problem #191

public class Solution {    static int hammingWeight(int n) {        int sum = 0;        while (n != 0) {            sum++;            n = n & (n - 1);//            n &= (n - 1);        }        return sum;    }    public static void main(String[] args) {        // Example 1:        int n1 = 0B00000000000000000000000000001011;        //  O/P: 3        // Example 2:        int n2 = 0B00000000000000000000000010000000;        //  O/P: 1        //  Need to signed number issue        // Example 3:        //Input: n3 = 11111111111111111111111111111101        //Output: 31        System.out.println(hammingWeight(n1));        System.out.println(Integer.toBinaryString(hammingWeight(n1)));        System.out.println(hammingWeight(n2));        System.out.println(Integer.toBinaryString(hammingWeight(n2)));    }}
Reverse Bits

↗ See LeetCode Problem #190

// Doesn't work with negative signed integerpublic class Solution {    static int reverseBits(int n) {        //   If n is 0 return 0        if (n == 0) {            return 0;        }        //   Initializing the result        int result = 0;        //   Loop through the given 32 bit (unsigned) integer        for (int i = 0; i < 32; i++) {            //  Bitwise leftshifting result            result <<= 1;            //  Adding 1 to result if & between righmost value of n            //      and 1 is 1            if ((n & 1) == 1) {                result++;            }            //   Bitwise righshifting given n since the rightmost digit            //       has been processed            n >>= 1;        }        return result;    }    public static void main(String[] args) {        // Example 1://        int n1 = 00000010100101000001111010011100;        int n1 = 0B00000010100101000001111010011100;        //  O/P: 964176192 (00111001011110000010100101000000)        //                 (111001011110000010100101000000)        // Example 2://        int n2 = 11111111111111111111111111111101;        //  Wrong since left-most 1 represents negative        //  int n2 = 0B11111111111111111111111111111101;        //  First, flip 1's and 0's: to get 1's complement        //  0B00000000000000000000000000000010;        //  Then add 1: to get 2's complement        //  0B00000000000000000000000000000011;        //  So, we have://        long n2 = 0B00000000000000000000000000000011L;        //  O/P: 3221225471 (10111111111111111111111111111111)        System.out.println(reverseBits(n1));        System.out.println(Integer.toBinaryString(reverseBits(n1)));//        System.out.println(reverseBits(n2));    }}
Single Number

↗ See LeetCode Problem #136

public class Solution {    static int singleNumber(int[] nums) {        int result = 0;        for (int i = 0; i < nums.length; i++) {            result ^= nums[i];        }        return result;    }    public static void main(String[] args) {        int[] nums1 = {2,2,1};        //  O/P: 1        int[] nums2 = {4,1,2,1,2};        //  O/P: 4        int[] nums3 = {1};        //  O/P: 1        System.out.println("Example 1: " + singleNumber(nums1));        System.out.println("Example 2: " + singleNumber(nums2));        System.out.println("Example 3: " + singleNumber(nums3));    }}
Sort Integers by the Number of 1 Bits

↗ See LeetCode Problem #1356

import java.util.Arrays;public class Solution {    public int[] sortByBits(int[] arr) {            int lengthArray = arr.length;        int[] oneBitsArray = new int[lengthArray];        //  Sort the given array in ascending order        //      since we have to return elements with        //      the same number of 1's in the ascending order        Arrays.sort(arr);        //  Iterate over the elements of a given array        //      to count the number of 1's in each (element)_2        //  Store the number of each element in oneBitsArray        for (int i = 0; i < lengthArray; i++) {            //  Declare and initialize the count of 1's            int countOneBits = 0;            //  Store the current array element            int currentElement = arr[i];            //  Iterative over the all bits in the            //      binary version of the current element            //      to count the total number of 1's            while (currentElement > 0) {                //  If 1 bit AND with currentElement yields 1                //      we have a 1, so countOneBits increased by 1                if ((currentElement & 1) == 1) {                    countOneBits++;                }                //  Once the current bit from the binary version                //      of current element is processed as above                //      we get rid of it with the right shift operator,                //      using >> (by 1 bit only)                currentElement >>= 1;            }            //  Add the current value of countOneBits            //      as the current element in oneBitsArray            oneBitsArray[i] = countOneBits;        }        //  Declare and initialize the resultArray to be returned        int[] result = new int[arr.length];        //  Declare and initialize index for result array to be returned        int resultIndex = 0;        //  Declare and initialize maximum number of bits        //      to be considered        //  This can be obtained from the contstraints        //      limiting the size of each element in the given array        //  There are 14 bits in 10000 (given constraint)        int maxBits = 14;        //  Iterate over all bits assuming a maximum possible value        //      of an element in binary representation        //  Start from 0 and loop through maxBits        //      for a maximum of maxBits number of 1's        for (int i = 0; i < maxBits; i++) {            //  Now, iterate over the array with the count of 1's            for (int j = 0; j < oneBitsArray.length; j++) {                //  If the count of 1's matches with the number of                //      possible 1's in the binary representation of                //      of an element in the given array (that is                //      already sorted in the beginning), then add                //      this number to the result array to be returned                if (oneBitsArray[j] == i) {                    //  Update the result by at current index                    //      and THEN increase the index by 1;                    //      hence post-increment                    result[resultIndex++] = arr[j];                }            }        }        //  Return the updated array        return result;    }    public static void main(String[] args) {        Solution solution = new Solution();        // Example 1:        int[] arr = new int[] {0,1,2,3,4,5,6,7,8};        System.out.println(Arrays.toString(solution.sortByBits(arr)));        //  O/P: [0,1,2,4,8,3,5,6,7]        System.out.println();        // Example 2:        arr = new int[] {1024,512,256,128,64,32,16,8,4,2,1};        System.out.println(Arrays.toString(solution.sortByBits(arr)));        //  O/P: [1,2,4,8,16,32,64,128,256,512,1024]    }}