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.

#include<stdio.h>

int main() {

	int a = 6;
	int b = 3;
	int c = a & b;
	printf("%d\n", c);
	return 0;
}

/* Explanation 

Decimal     Binary
a = 6       110
b = 3       011
           ------
c           010  ( which is 2 in decimal )
*/
  • Bitwise or operator ( | )

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

#include<stdio.h>

int main() {

	int a = 6;
	int b = 3;
	int c = a | b;
	printf("%d\n", c);
	return 0;
}

/*
Explanation:

    Decimal     binary
a = 6            110
b = 3          | 011
               -------
c                111
*/
  • 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

#include<stdio.h>

int main() {

	int a = 6;
	int b = 3;
	int c = a ^ b;
	printf("%d\n", c);
	return 0;
}

/*
Explanation:

    Decimal     binary
a = 6            110
b = 3          ^ 011
               -------
c                101
*/
  • (~) Bitwise Complement operator ( It inverts the bits of a binary number)

Let us see below example and look at its output.

#include<stdio.h>

int main() {

	int a = 6;
	int c = ~a;
	printf("%d\n", c);
	return 0;
}

/* output 
   -7
 */
  • 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.

#include<stdio.h>

int main() {

	int a = 6;
	int c = a << 1;
	printf("%d\n", c);
	return 0;
}

/* Explanation:
  Decimal     binary
  a = 6       110
              << 1
             1100   ( 1×2^3 + 1×2^2 + 0x2^1 + 0x2^0 = 12 )
 
 */

/* output
   12
 */

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.

#include<stdio.h>

int main() {

	int a = 6;
	int c = a >> 1;
	printf("%d\n", c);
	return 0;
}

/* Explanation:
  Decimal     binary
  a = 6       110
              >> 1
              011  ( 0×2^2 + 1x2^1 + 1x2^0 = 3 )

 */

/* output
   3
 */

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



Related Contents to follow