Bitwise Tricks Or Regret Later

Tricks 1 : check if a number is a power of 2 using its binary representation in C++

A number is a power of 2 if it has exactly one bit set to 1 in its binary representation. You can use the following approach to check this:

  • A power of 2 number has only one set bit. For example:
    • 2^0 = 1 → 0001
    • 2^1 = 2 → 0010
    • 2^2 = 4 → 0100

To check this, you can use the property:

  • If n is a power of 2, then (n & (n - 1)) will be 0.

Here’s the C++ code for checking if a number is a power of 2 using this idea:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
using namespace std;

int main()
{
    int num;
    cout << "Enter a number: ";
    cin >> num;

    // Check if the number is positive and a power of 2
    if (num > 0 && (num & (num - 1)) == 0)
    {
        cout << num << " is a power of 2." << endl;
    }
    else
    {
        cout << num << " is not a power of 2." << endl;
    }

    return 0;
}

Tricks 2: Playing with the k th bit

  • Check if k-th bit is set: You can use the bitwise AND operator to check if the k-th bit is set (1).{x&(1«k)}

    1
2
3

      bool isKthBitSet(int n, int k) {
      return (n & (1 << (k - 1))) != 0;
  }

    This shifts the number 1 to the left by k-1 positions, and then the bitwise AND checks if that bit in n is 1.

  • Set the k-th bit: To set the k-th bit (turn it into 1), you use the bitwise OR operator. {x or (1«k)}

    1
2
3

      int setKthBit(int n, int k) {
      return n | (1 << (k - 1));
  }

    This ensures the k-th bit is set to 1, leaving other bits unchanged.

  • Clear/unset the k-th bit: To clear the k-th bit (turn it into 0), use the bitwise AND with the complement of the shifted bit.{x&n(1«k)}

    1
2
3

      int clearKthBit(int n, int k) {
      return n & ~(1 << (k - 1));
  }

    The expression ~(1 << (k - 1)) generates a mask that has all bits set to 1 except the k-th bit, which is 0.

  • Toggle the k-th bit: To toggle the k-th bit (flip it from 1 to 0 or 0 to 1), use the bitwise XOR operator.{X^(1«k)}

    1
2
3

      int toggleKthBit(int n, int k) {
      return n ^ (1 << (k - 1));
  }

  • Turn off all bits except the k-th: This keeps only the k-th bit turned on (if set) and turns off all other bits.

    1
2
3

      int keepOnlyKthBit(int n, int k) {
      return n & (1 << (k - 1));
  }

Tricks 3: Multiply or Divide a number by $k^2$

Multiply by $2^k$: (Left shift (<<)is used to multiply a number by $2^k$)

To multiply a number by $2^k$, use the left shift operator (<<).

Code:

1
2
3

int multiplyByTwoPowerK(int n, int k) {
    return n << k;
}

Explanation:

  • n << k shifts the bits of n to the left by k positions. This is equivalent to multiplying n by 2k.
  • For example, n << 3 is equivalent to multiplying n by 23=8.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>
using namespace std;
int multiplyByTwoPowerK(int n, int k) {
    return n << k;
}

int main() {
    int n = 5;
    int k = 3;

    cout << "5 multiplied by 2^3 is: " << multiplyByTwoPowerK(n, k) <<endl; // Output: 40

    return 0;
}

Output:

1
2

5 multiplied by 2^3 is: 40

Divide by $2^k$:(Right shift (>>)is used to divide a number by $2^k$)

To divide a number by $2^k$, use the right shift operator (>>).

Code:

1
2
3

int divideByTwoPowerK(int n, int k) {
    return n >> k;
}

Explanation:

  • n >> k shifts the bits of n to the right by k positions. This is equivalent to dividing n by 2k (ignoring the remainder for integers).
  • For example, n >> 3 is equivalent to dividing n by 23=8.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
using namespace std;
int divideByTwoPowerK(int n, int k) {
    return n >> k;
}

int main() {
    int n = 40;
    int k = 3;

    cout << "40 divided by 2^3 is: " << divideByTwoPowerK(n, k) <<endl; // Output: 5
    return 0;
}

Output:

1

40 divided by 2^3 is: 5

Tricks 4: Find out x % $2^k$

To find x % 2^k using bitwise operations in C++, you can use the fact that modulo by a power of 2 can be computed efficiently using a bitwise AND operation.

Given that 2^k is a power of 2, its binary representation is a 1 followed by k zeros. So, x % 2^k is equivalent to taking the lowest k bits of x, which can be done with the following expression:

1

x & ((1 << k) - 1)

Here’s a breakdown of how this works:

  • 1 << k shifts 1 to the left by k positions, which gives 2^k.
  • Subtracting 1 from 2^k gives a number with the lowest k bits set to 1.
  • Performing a bitwise AND between x and this mask effectively keeps the lowest k bits of x (which gives you x % 2^k).

Example code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
using namespace std;

int main() {
    int x = 29;  // Example value
    int k = 3;   // Example value for k

    int result = x & ((1 << k) - 1);

    cout << x << " % " << (1 << k) << " = " << result << endl;

    return 0;
}

Explanation:

  • For x = 29 (which is 11101 in binary) and k = 3, you want to find 29 % 2^3 = 29 % 8.
  • 1 << 3 gives 8 (which is 1000 in binary).
  • 8 - 1 gives 7 (which is 111 in binary).
  • 29 & 7 gives 5 (which is 101 in binary), so 29 % 8 = 5.

This approach is efficient and works in constant time.

Tricks 5: Swap two numbers, X and Y, without a temporary variable

You can swap two numbers, X and Y, without using a temporary variable using bitwise XOR. Here’s how it works:

Explanation:

The XOR operation has the following properties:

  • A ^ A = 0
  • A ^ 0 = A
  • A ^ B ^ A = B (XOR is commutative and associative)

Using these properties, the following steps swap X and Y:

  1. X = X ^ Y; (Now X holds the result of X ^ Y)
  2. Y = X ^ Y; (Since X = X ^ Y now, Y = (X ^ Y) ^ Y = X—so Y holds the original value of X)
  3. X = X ^ Y; (Now X = (X ^ Y) ^ X = Y—so X holds the original value of Y)

C++ Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
using namespace std;

int main() {
    int X = 5;
    int Y = 10;

    // Before swapping
    cout << "Before swapping: X = " << X << ", Y = " << Y << endl;

    // XOR swap algorithm
    X = X ^ Y;
    Y = X ^ Y;
    X = X ^ Y;

    // After swapping
    cout << "After swapping: X = " << X << ", Y = " << Y << endl;

    return 0;
}

Output:

1
2
3

Before swapping: X = 5, Y = 10
After swapping: X = 10, Y = 5

This method uses only bitwise XOR operations and does not require any extra memory or temporary variables.

Tricks 6:

1
2
3
4
5
6

 property: no. of set bits in A = X
           no. of set bits  in B = Y
           no. of set bit in (A^B) = Z
Then,
       z is even if x+y is even
       z is odd of x+y is odd`

The property you’re describing relates to the number of set bits in the binary representation of numbers A, B, and their XOR result (A ^ B).

Here’s how it works:

  • The number of set bits in A is denoted by X.
  • The number of set bits in B is denoted by Y.
  • The number of set bits in (A ^ B) is denoted by Z.

The XOR Operation and Set Bits:

  • The XOR operation results in 1 only when the bits of the two numbers differ.
  • If both A and B have the same bit in a particular position (either 0 or 1), XOR will result in 0 for that position.
  • Thus, the number of set bits in (A ^ B) depends on how different the bit patterns of A and B are.

The property:

  • If X + Y is even, Z (the number of set bits in (A ^ B)) is even.
  • If X + Y is odd, Z is odd.

C++ Code to Check:

You can use the following C++ code to verify this property:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
using namespace std;

// Function to count the number of set bits in a number
int countSetBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;  // Increment count if the least significant bit is 1
        n >>= 1;         // Right shift n by 1 bit
    }
    return count;
}

int main() {
    int A = 5;  // Example value
    int B = 10; // Example value

    int X = countSetBits(A);     // Number of set bits in A
    int Y = countSetBits(B);     // Number of set bits in B
    int Z = countSetBits(A ^ B); // Number of set bits in A ^ B

    cout << "Set bits in A (X): " << X << endl;
    cout << "Set bits in B (Y): " << Y << endl;
    cout << "Set bits in (A ^ B) (Z): " << Z << endl;

    if ((X + Y) % 2 == 0) {
        cout << "Since X + Y is even, Z is even: " << ((Z % 2 == 0) ? "True" : "False") << endl;
    } else {
        cout << "Since X + Y is odd, Z is odd: " << ((Z % 2 != 0) ? "True" : "False") << endl;
    }

    return 0;
}

Explanation:

  • The countSetBits function counts the number of set bits (1’s) in the binary representation of a number by repeatedly checking the least significant bit using n & 1 and right-shifting the number by 1 bit.
  • The program then checks the property: If X + Y is even, Z is even, and if X + Y is odd, Z is odd.

Example:

For A = 5 (binary 101), B = 10 (binary 1010):

  • X = 2 (two 1’s in 101)
  • Y = 2 (two 1’s in 1010)
  • A ^ B = 15 (binary 1111, four 1’s), so Z = 4.

Since X + Y = 2 + 2 = 4 is even, Z is even, and the output will confirm this.