home

Bit Manipulation

Table of Contents

Find ith bit

5 -> 101

3rd bit:

101 & 100 -> 100 

#include<stdio.h>

int main() {
    int n = 5;

    // print 1st bit from right
    printf("%d\n", (n&(1<<0)) >> 0);
    // print 2nd bit from right
    printf("%d\n", (n&(1<<1)) >> 1);
    // print 3rd bit
    printf("%d\n", (n&(1<<2)) >> 2);

    // or
    printf("%d\n", (n >> 0) & 1);
    printf("%d\n", (n >> 1) & 1);
    printf("%d\n", (n >> 2) & 1);
}

1
0
1
1
0
1

Set ith bit

set 2nd bit in 5 (101)

101 | 010 -> 111 (7) 

#include<iostream>

using namespace std;

int main() {
    int n = 5;

    cout << (n | (1 << 1)) << endl;
}

7

set 4th bit in 10 (1010) (already set!)

1010 | 1000 -> 1010 

#include<iostream>

using namespace std;

int main() {
    int n = 10;

    cout << (n | (1 << 3)) << endl;
}

10

clear (or unset) ith bit

clear 3rd bit in 5 (101)

101 & 011 -> 001 (1) 

#include<iostream>

using namespace std;

int main() {
    int n = 5;
    cout << (n & (~(1 << 2))) << endl;
}

1

clear 4th bit in 10 (1010)

1010 | 0111 -> 0010 

#include<iostream>

using namespace std;

int main() {
    int n = 10;
    cout << (n & (~(1 << 3))) << endl;
}

2

count set bits in a number

101 (5) has 2 set bits 1010 (10) has 2 set bits 1110 (14) has 3 set bits

To get number of bits in a binary number:

  • log2(n)+1 (floored value)

To get number of digits in a decimal number:

  • log10(n)+1 (floored value)

An iterative approach would be to loop while n != 0 and check the last bit and increment a counter if it's 1. After the check, right shift n. The time complexity would be O(log2(n) + 1). 

int count = 0;
while (n != 0) {
    if (n & 1 == 1) count++;
    n = n >> 1;
}

However, a faster approach would be: 

int count = 0;
while (n != 0) {
    count++;
    n = n & (n - 1);
}

The above algorithm runs only n times where n is the number of set bits. 

#include<iostream>

using namespace std;

int main() {
    int n = 5;
    int i = 10;
    int j = 14;

    int count = 0;
    while (j != 0) {
        count++;
        j = j & (j - 1);
    }

    cout << count << endl;
}

3

Find number of bits that have to change to convert a number a to number b

We can simply ^(XOR) the two numbers to find out different bits in the two numbers that should be changed. We can then count the set bits of the result of the XOR operation to find the number of bits that have to be changed. 

#include<iostream>
using namespace std;

int main() {
    int a = 10;
    int b = 5;

    int x = a ^ b;

    int count = 0;
    while (x != 0) {
        count++;
        x = x & (x - 1);
    }

    cout << count << endl;
}

4

The XOR operator

Properties

  • n ^ n is 0. E.g. 5 ^ 5 = 0.
  • 0 ^ n is n. E.g. 0 ^ 5 = 5.

Find the only non repeating element in an array where every element repeats twice

Given. arr = [5, 4, 1, 3, 1, 4, 5]

Expected answer: 3

Approach one (O(n2) time and O(1) space)

two loops (nested), for every arr[i] check if there exists another number at arr[j] such that arr[i] == arr[j] (where j != i). If there is a number move on, else arr[i] would be the answer. 

arr = [5, 4, 1, 3, 1, 4, 5]

ans = -1

for i in range(0, len(arr)):
    val = arr[i]
    found = False
    for j in range(0, len(arr)):
        if (arr[i] == arr[j] and i != j):
            found = True
            break
    if (not found):
        ans = arr[i]
        break

print(ans)

3

Approach two (O(n) time and O(n - 1) space)

Use a hash set. Find element in set for every n. If found, remove n from set, else add n to the set. In the end there should be only one element in the set that should be the answer. 

#include<iostream>
#include<vector>
#include<unordered_set>

using namespace std;

int main() {
    vector<int> input = {5, 4, 1, 3, 1, 4, 5};
    unordered_set<int> s;

    for (int i = 0; i < input.size(); ++i) {
        auto it = s.find(input[i]);
        if (it != s.end()) {
            s.erase(input[i]);
        } else {
            s.insert(input[i]);
        }
    }

    cout << *s.begin() << endl;
}

3

Approach three: using XOR (O(n) time and O(1) space)

arr = [5, 4, 1, 3, 1, 4, 5]

We have:

  1. 0 ^ n -> n
  2. n ^ n -> 0

If we do:

res = 0; res ^= arr[i];

Then 

res = 0 ^ 5 ^ 4 ^ 1 ^ 3 ^ 1 ^ 4 ^ 5;
    = 5 ^ 4 ^ 1 ^ 3 ^ 1 ^ 4 ^ 5;
    rearranging like numbers gives:
    = 5 ^ 5 ^ 4 ^ 4 ^ 1 ^ 1 ^ 3;
    =   0   ^   0   ^   0   ^ 3;
    = 0 ^ 3;
    = 3;

#include<iostream>
#include<vector>

using namespace std;
int main() {
    vector<int> arr = {5, 4, 1, 3, 1, 4, 5};
        int res = 0;

    for (auto &i:arr) {
        res ^= i;
    }

    cout << res << endl;

}

3

Find two non repeating element in an array where every element repeats twice

Given. arr = [5, 4, 1, 4, 3, 5, 1, 2]

Expected answer: 3, 2

If we follow the approach from the previous question, we'll get:

temp = 3 ^ 2;

We want to separate these two operands to the XOR op. To do that, we do:

  1. get the position of the least significant set bit of temp;
  2. divide the array in two subarrays where one subarray has set bit at that that position and the other has unset bit at that position.;
  3. perform XOR on all elments and temp of for both subarrays to get two numbers that'll be 3 and 2 in this case;
  4. 3 ^ 2 = 0001 (0011 ^ 0010). least significant set bit's position is 1 (from right); Get it using bit = temp & ~(temp - 1).
  5. Two subarrays will be: [5, 1, 3, 5, 1] and [4, 4, 2]
  6. (3 ^ 2) ^ 5 ^ 1 ^ 3 ^ 5 ^ 1 = 2 and (3 ^ 2) ^ 4 ^ 4 ^ 2 = 3. The answer is 2 and 3.
#include<iostream>
#include<vector>

using std::vector;

int main() {
    vector<int> arr = {5, 4, 1, 4, 3, 5, 1, 2};
    int temp = 0;
    for (int &i : arr) {
        temp ^= i;
    }

    // temp -> 3 ^ 2;

    int set_bit = temp & ~(temp - 1);
    int a = temp, b = temp;

    for (int &i : arr) {
        if (i & set_bit) {
            a ^= i;
        } else {
            b ^= i;
        }
    }

    std::cout << a << " " << b << std::endl;
}

TODO Find the only non repeating element in an array where every element repeats k times.

Given. arr = [2, 2, 1, 5, 1, 1, 2]

Expected answer: 5

Author: Siddhant Kumar