List of Bitwise operators

1. & ( Bitwise AND )

2. | ( Bitwise OR )

3. ~ ( Bitwise NOT )

4. ^ ( Bitwise XOR )

5. << ( Bitwise Left Shift )

6. >> ( Bitwise Right Shift )

7. >>> ( Bitwise unsigned Right shift )

8. &= ( Bitwise AND Assignement )

9. |= ( Bitwise OR Assignment )

10. ^= ( Bitwise XOR Assignment )

11. <<= ( Bitwise left shift and assignment )

12. >>>= ( Bitwise unsigned right shift and assignment )

First, some bitwise operators you've used before looking like logical operators ( & vs &&, | vs || )

second, most bitwise operators come with a compound assignment form of themselves. This is the same as using + and +=, - and -=, etc.

Well, in this article we are going to indulge in the application of bitwise operators.

• Bitwise AND ( & )

Observation👀: When you &1 with any number, digits remain the same.

    110010100
&   111111111
________________
    110010100

Q.) Given a number n, find if it's odd or even.

( 19 ) base 10 = ( 10011 ) base 2

If the last digit of any number when & with 1 is 1 then it is odd otherwise even.

An example is shown above.

Pseudo Code : n & 1 == 1 => odd else even

Q.) Convert ( 17 ) base 10 to base 2

Keep dividing by base, take the remainder, and write in the opposite.

Pseudo Code : while ( n > 0 ){
                rem = rem * 10 + ( n % 2 );
                n / = 2;
                }

# rem is containing the binary numbers of that particular number provided.

• Bitwise Left Shift Operator ( << )

  ( 10 ) base 10 = ( 1010 ) base 2

  1010 << 1 = 10100 --- ( just added 0 )

  10100 = 1 * 2^4 + 0 2^3 + 1 * 2^2 + 0 \ 2^1 + 0 * 2^0*

  \= 16 + 0 + 4 + 0 + 0

  \= 20

  Observation👀: If you want to double the number left shift by 1.

Q.) Find the ith bit. ( Let i = 5)

    10110110
  & 00010000
_______________
    00010000

# This is called masking.

Pseudo Code : n & ( 1 << ( n - 1 ) )

• Bitwise OR operator ( | )

Q.) Set the ith bit i.e., turning the ith bit from 0 to 1.

    1010110
  | 0001000
_____________
    1011110

Pseudo Code: ( n | ( 1 << ( n - 1 ) ) )

Note: Bitwise operators are also associative i.e., 2 3 4 = 3 4 2 = 4 3 2 similarly, 2 ^ 3 ^ 4 = 3 ^ 4 ^ 2 = 4 ^ 3 ^ 2

Q.) Reset the ith bit ( let i = 5 )

    1010110
 &  1101111
_____________
    1000110

Pseudo Code : ! ( 1 << ( n - 1 ) )

• Bitwise XOR operator ( ^ )

Observation👀: a ^ 1 = ~ a , ( 0 ^ 1 = 1 , 1 ^ 1 = 0)

Q.) Finding the number which has no pair in a given array.

arr = { 2, 3, 4, 1, 2, 1, 3, 6, 4 }

Note: XOR all the numbers.

int unique = 0;
for ( int n : arr ) {
        unique ^ = n;
}
// unique contains the unpair number

• Bitwise Complement operator ( ~ )

  a = 10110

  ~a = 01001

  Q. ) Find the negative of a given number ( binary number )

  steps

  1. Complement of number

  2. Add 1 to it

  Example : ( 10 ) base 10 = ( 00001010 ) base 2

    1)     11110101 ----- complement of number 00001010
    2)    +       1 ----- Adding 1 to it
        _____________
            11110110
            = ( - 10 )
  
    Pseudo Code : ~ N + 1
  

  • Bitwise Right shift operator ( >> )

    0011001 >> 1 => 001100

    a >> b = a / 2 ^ b

    Q.) Find the nth magic number

    1 = 001 = 5

    2 = 010 = 25

    3 = 011 = 30

    Observation👀: 1 = 001

    *= 0 5 ^ 3 + 0 5 ^ 2 + 1 5 ^ 1

    = 5

      Pseudo Code : int n = 6;
                    int ans = 0;
                    int base = 5;
                    while ( n > 0 ) {
                      int last = n & 1;
                      n = n >> 1;
                      ans += last * base;
                      base = base * 5;
                  }
      // ans contains the nth magic number
    

    Q.) Pascal's Triangle

    1

    1 1

    1 2 1

    1 3 3 1

    1 4 6 4 1

    Find the sum of the nth row.

    Answer: Sum of nth row = nC0 + nC1 + nC2 + .......... + nCn = 2 ^ n

    For nth row , sum = 2 ^ n - 1

      Pseudo Code: 1 << ( n - 1 )
    

    Q.) XOR of all numbers between a and b.

    a = 3, b = 9

    ans = 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9

      main () {
          ans = XOR ( b ) ^ XOR ( a - 1 );
          }
      func XOR ( int a ) {
           if ( a % 4 == 0 ) {
              return a;
            }
          if ( a % 4 == 1 ) {
              return 1;
             }
          if ( a % 4 == 2 ) {
              return a + 1;
              }
          return 0;
      }
    
      // ans contains the XOR of all numbers between a and b.
    

    I hope you all enjoyed learning bitwise operators in an alternate way.

    If you have made it this far, I hope you have enjoyed this article. Please give any suggestions or feedback to help me improve my writing.

    Thank you! 💫✨