1. Courses
  2. Programming
  3. Bit Manipulation
Go To Problems

Level 3

Bit Manipulation

What is binary number system

Understanding data types - int

Bitwise operators

As we discussed in the previous video, the numbers are stored in their binary representation in computers and every single digit 0 / 1 is called bit.
Most languages allow you to perform operations which are bitwise ( this statement will make much more sense when we look at the operator themselves ). It is a fast, primitive action directly supported by the processor, and is used to manipulate values for comparisons and calculations.

Bitwise AND :
Syntax :
A & B
Values for bit combinations
            a      b         a & b 
           ------------------------
            0      0         0
            0      1         0
            1      0         0
            1      1         1

In other words, a & b = 0 unless a = 1 and b = 1.

What does A & B mean :

A & B implies a & b for all corresponding bits of A and B.

So, lets say,

       A = 21 ( 10101 ) and B = 6  ( 110 ) 
       A & B = 
                        1 0 1 0 1
                    &   0 0 1 1 0  
                    ------------------
                        0 0 1 0 0  =  4.
Bitwise OR :
Syntax :
A | B
Values for bit combinations
            a      b      a | b 
           ------------------------
            0      0         0
            0      1         1
            1      0         1
            1      1         1

In other words, a | b = 1 unless a = 0 and b = 0

What does A | B mean :

A | B implies a | b for all corresponding bits of A and B. So, lets say

       A = 21 ( 10101 ) and B = 6  ( 110 ) 
       A | B = 
                        1 0 1 0 1
                    |   0 0 1 1 0  
                    ------------------
                        1 0 1 1 1  =  23.
Bitwise XOR :
Syntax :
A ^ B
Values for bit a, b :
            a      b      a ^ b 
          ------------------------
            0      0         0
            0      1         1
            1      0         1
            1      1         0

In other words, a ^ b = 1 when a and b are different.

What does A ^ B mean :

A ^ B implies a ^ b for all corresponding bits of A and B. So, lets say

       A = 21 ( 10101 ) and B = 6  ( 110 ) 
       A ^ B = 
                        1 0 1 0 1
                    ^   0 0 1 1 0  
                    ------------------
                        1 0 0 1 1  =  19.
Bitwise NOT :
Syntax :
~A
Values for bit a :
                                a   |   ~a
                             -------|-------
                                0   |   1
                                1   |   0

Its the inverse of the bit.

What does ~A mean

~A implies inverting every single bit in A. So, lets say

            A = 21 ( 10101 ) and A is a char ( 1 byte )
            ~A = 
                0 0 0 1 0 1 0 1
              --------------------------
                1 1 1 0 1 0 1 0  = -22 ( Sign bit is 1 ).

Bitwise operators ( contd.. )

Right Shift Operators :
Syntax :
A >> x
What does A » x mean :

A >> x implies shifting the bits of A to the right by x positions. The last x bits are lost this way.

Example : Lets say

                A = 29 ( 11101 ) and x = 2, 
                so A >> 2 means
                     0 0 1 1 1 0 1 >> 2
                               ====  -> is lost 
                    ========== -----> this sequence of digit shifts to the right by 2 positions
                    ----------------
                     0 0 0 0 1 1 1 = 7

A >> x is equal to division by pow(2, x). Think why.

Left shift operators :
Syntax :
A << x
What does A « x mean :

A << x implies shifting the bits of A to the left by x positions. The first x bits are lost this way. The last x bits have 0. Example : lets say

                A = 29 ( 11101 ) and x = 2, 
                so A << 2 means
                     0 0 1 1 1 0 1 << 2
                     =============  ------> this sequence of digit shifts to the left by 2 positions
                    ----------------
                     1 1 1 0 1 0 0  = 116

A << x is equal to multiplication by pow(2, x). Think why. 1 << x is equal to pow(2, x).

Tricks with bits

  • x & (x-1) will clear the lowest set bit of x
  • x & ~(x-1) extracts the lowest set bit of x (all others are clear). Pretty patterns when applied to a linear sequence.
  • x & (x + (1 << n)) = x, with the run of set bits (possibly length 0) starting at bit n cleared.
  • x & ~(x + (1 << n)) = the run of set bits (possibly length 0) in x, starting at bit n.
  • x | (x + 1) = x with the lowest cleared bit set.
  • x | ~(x + 1) = extracts the lowest cleared bit of x (all others are set).
  • x | (x - (1 << n)) = x, with the run of cleared bits (possibly length 0) starting at bit n set.
  • x | ~(x - (1 << n)) = the lowest run of cleared bits (possibly length 0) in x, starting at bit n are the only clear bits.

Bitwise and Logical Operators :

  • Now that you have learnt about bitwise operators, you must have realized & is very different from &&. Similarily | is very different from ||
  • & or | work on integers performing the operator on each corresponding bits. However, && or || work on boolean values ( Any non zero value is true ) to produce a boolean result.

Example :

   2  |   1  = 3
   2  ||  1  = true
   2   &  1  =  0
   2  &&  1  = true
  • Very similar to the fact that
    you can rewrite A = A + B as A += B,
    you can rewrite
    A = A | B as A |= B or
    A = A & B as A &= B
Previous Next
  • 1. What is binary number system
  • 2. Understanding data types - int
  • 3. Bitwise operators
  • 4. Bitwise operators ( contd.. )
  • 5. Tricks with bits
  • 6. Bitwise and Logical Operators :
Bucketing
Problem Score Companies Time Status
Min XOR value 200
Booking.com
33:22
Bit play
Problem Score Companies Time Status
Number of 1 Bits 200
Adobe
8:08
Reverse Bits 225
NvidiaHCLAmazon
21:33
Divide Integers 250
Amazon
52:23
Different Bits Sum Pairwise 300
42:49
Bit array
Problem Score Companies Time Status
Single Number 275
Amazon
10:56
Single Number II 275
Amazon
34:29