bit manipulation in c or c++ programming is an operation where we manipulate the bits or pattern of bits. In competitive programming  if anyone is expert of manipulating bits then one can achieve an efficient solution. In this blog post we will study the basics of bit manipulation and later on see it’s usefulness in competitive programming.

Basics of bit manipulation in c/c++

  • Bitwise and operator (&)

    If a = 6 and b = 3 , then bitwise a & b would be 2.  Bitwise & operator outputs 1 if both bits are 1, otherwise it outputs 0. Look at below example.

  • Bitwise or operator ( | )

If any bit of two binary numbers is 1 position wise, then bitwise or operator ( | ) , results 1. See below example.

  • Bitwise exclusive-or ( ^ )

Bitwise exclusive or operator is equivalent to X-Or gate of electronics. If any of bits of binary numbers are same position wise then it results 0, other wise it results 1. 

Example for bitwise Exclusive-Or

  • (~) Bitwise Complement operator ( It inverts the bits of a binary number)

Let us see below example and look at its output.

  • Why ~6 becomes -7?  because negative numbers are represented as two’s complement.Let us see, 6 is the binary value0110And ~6 flips the bits so the value is now:1001

    Which, is the binary representation of -7. But How ?

    How -7 would be represented as 2’s complement:

    (1) binary equivalent of positive 7:

    0111

    (2) Flips the bits

    1000

    (3) add 1,to become negative
        1001 ( -7 )

  • Bitwise left shift operator ( << )

Bitwise left shift moves all the bits to the left. It fills vacant position with 0s. see below example and observe input and output.

Note: Left shifting a number means multiply by number of shifts.

  • Bitwise right shift operator

Bitwise right shift moves all the bits to the right.see below example and observe input and output.

Note: Right shifting a number means divide by number of shifts. Learn our next blog some-uses-of-bit-manipulation




Related Contents to follow