Getting started with Bits

We all know how a doubly linked list works and about its memory inefficiency. But what if I say that a doubly linked list can be implemented in the same space complexity as a singly linked list using some simple bitwise operation? Yes, you heard it right! Bit manipulation is something that comes in handy when we have to optimize something. Here, instead of storing the original memory address, we store the bitwise XOR of the previous and next node, hence reducing the space of one address in each node.

What is Bit Manipulation?

Bit manipulation is the technique of manipulating the data on a bit level using bitwise operators. As computers typically store integers in two’s complement form, working directly on bits makes the operation faster than normal arithmetic operations. Once you get the hang of them, this can be applied to a huge variety of problems, however, always make sure not to compromise on the readability of the code by applying these techniques.

In this article, we will explore the basics of bitwise operations and certain cool code snippets using bits that can make our code elegant and faster.

Bitwise operators

Bitwise operators enable you to manipulate the individual raw data bits within a data structure. Let’s see different types of bitwise operators-

Bitwise AND: The bitwise AND operator (&) takes the logical AND of the bits in each position of a number in binary form, that is, it gives 1 only if both bits are equal to 1.

For example:101 & 111 is equal to 101 as both bits become one only in ones and hundreds place.

Bitwise OR: The bitwise OR operator (|) works the same as Bitwise AND. The difference is only one of the bits needs to be 1 for that position’s bit in the output to be 1.

For example:101 | 111 is equal to 111 as both bits never became zero together.

Bitwise NOT: Unlike other bitwise operators bitwise NOT operator (~) takes only one operand and inverts all bits in it, that is, one’s complement of the number.

For example: ~101 = 010.

Bitwise XOR: The bitwise XOR operator or “exclusive OR operator” (^) compares the bits of two numbers one by one and gives 1 only if both bits are different.

For example:101 ^ 111 is equal to 010 as both bits differ only at tens place.

Left Shift: Left shift operator (<<) is a binary operator which shifts the bits of a number to the left and appends zero at the end. Interestingly, this is equivalent to multiplying the number by powers of two.

For example:110 << 1 = 1100
That is, 6<<1 is equal to 12, multiplication by 2.

Right Shift: Right shift operator (>>) is a binary operator which shifts the bits of a number to the right. If we observe closely, this is equivalent to dividing the number by powers of two.

For example:110 >> 1 = 11
That is, 6 >> 1 is equal to 3, division by 2.

Tricks With Bits

Let’s see some awesome bit hacks which make use of these concepts.

1. To get K-th bit from right

int getBit(int num, int k) {
    return num & (1<< (i-1));
}

2. SET the K-th bit from right

void setBit(int &n, int k) {
    n = n|(1<< (k-1));
}

3. Toggle the K-th bit from right in a number

void toggle(int &n, int k) {
    n = n ^ (1 << k - 1);
}

4. Check if two numbers are equal

bool equal(int a, int b) {
    if (a ^ b == 0)
        return True;
    return False;
}

5. Check if a number is a power of 2

bool isPowerof2(int number) {
    if (number & (number-1) ==0)
        return True;
    return False;
}

6. Check if a number is even or odd

bool isEven (int number) {
    if(number & 1 == 0)
        return True;
    return False;
}

7. Find the Greatest Common Divisor of two numbers

int gcd(int a, int b){
    while(b){
        b^=a^=b^=a%=b;
    }
    return a;
}

8. Swap two integers a and b

void swap(int &a, int &b){
    a^=b;
    b^=a;
    a^=b;
}

9. Minimum of x and y

int minimum(int x, int y){
    int min = (y ^ (x ^ y) & - (x < y));
    return min;
}

10. Maximum of x and y

int maximum(int x, int y){
    int max= (x ^ (x ^ y) & - (x < y));
    return max;
}

Practice problem links

Swap all odd and even bits
Max Consecutive Ones III
Next Greater Element III
Minimum Flips to Make a OR b Equal to c
Converting a Real Number (between 0 and 1) to Binary String

Resources

XOR Linked List — A Memory Efficient Doubly Linked List | Set 1
Bit Twiddling Hacks
That XOR Trick
Bitwise operations 2 — popcount & bitsets

Thanks for reading this article!