Skip to main content

BIT-Manipulation

 The bits work faster by reducing your execution time as it is the greatest factor in competitive programming. Faster the execution time better the code performance. So, let’s know about the major hacks that can be done at a bit level to optimise the code.

Useful operators for bit manipulation:

  • The & (bitwise AND) takes two operands and perform AND operation. It results in 1 if both numbers are the same else 0.
  • The | (bitwise OR) takes two operands and perform OR operation. It results in 1 when both bits are different.
  • The ^ (bitwise XOR) takes two number as operands and perform XOR operation. It results in 1 if both bits are different.
  • The << (left shift) takes two numbers, left shifts the bits of the first operand, the second operand decides the number of places to shift. Or in other words, left shifting an integer “x” with an integer “y” (x<<y) is equivalent to multiplying x with 2^y (2 raised to power y).
  • The >> (right shift) takes two numbers, right shifts the bits of the first operand, the second operand decides the number of places to shift. Similarly right shifting (x>>y) is equivalent to dividing x with 2^y.

Now let’s head on towards the bit hacks

  • Invert every bit of the number: We can invert every bit of the number using ~ operator. It is the one’s complement of the number. It becomes easier to calculate the 2’s complement by adding 1 i.e, (~num+1).

Example:

#include<iostream>

using namespace std;
int main()
{
int num = 4;
cout << (~num); // -5
return 0;
}

  • Check whether n is even or odd: The naive approach to check a number is even or odd is to take the modulo with 2. The better and efficient method is to take the (n&1). If the last bit is set n is odd, else even.

Example:

11 in binary format 1101
&

1 in binary format 0001

                               0001 --> last bit is set hence odd n.

14 in binary format 1110
&

1 in binary format 0001

                               0000 --> last bit is not set hence even n.

Code Implementation:

#include<iostream>

using namespace std;
// Returns true if
// n is even
bool isEven(int n)
{
return (!(n & 1));
}
int main()
{
int n = 101;
isEven(n) ? cout << “Even” : cout << “Odd”;
return 0;
}

  • How to set a bit in num: We can set a bit at the nth position in num by using the OR operator. First, we will left shift the bit from 1 to n via (1<<n). Then we use OR to set the bit in num.

Example:

#include<iostream>

using namespace std;
void set(int & num,int pos)
{
// (1<<pos) shifting 1 to the pos
num |= (1 << pos);
}
int main()
{
int num = 4, pos = 1;
set(num, pos);
cout << (int)(num) << endl;
return 0;
}

Output:
6

• How to clear a bit at the nth position in num
We can unset a bit at the nth position ‘num’ with the help of ‘AND’ (&) operator.
• Left shift ‘1’ to n position via (1<<n)
• Use bitwise NOT operator ‘~’ to unset this shifted ‘1’.
• Now after clearing this left-shifted ‘1’ i.e making it to ‘0’ we will ‘AND'(&) with the number ‘num’ that will unset bit at the nth position.

Example:

#include<iostream>

using namespace std;
// First step is to get a number that has all 1’s except the given position.
void unset(int &num,int pos)
{
//Second step is to bitwise and this number with given number
num &= (~(1 << pos));
}
int main()
{
int num = 7;
int pos = 1;
unset(num, pos);
cout << num << endl;
return 0;
}

  • Toggling a bit at nth position: We can toggle a bit (i.e, set to unset and vice versa). We use the XOR operator to do this purpose because it returns 1 if two bits are odd otherwise 0. The first step will be to shift 1 and then xor with the number.

Example:

#include<iostream>

using namespace std;
void toggle(int &num,int pos)
{
num ^= (1 << pos);
}
int main()
{
int num = 4;
int pos = 1;
toggle(num, pos);
cout << num << endl; // outputs 6
return 0;
}

  • Checking if the nth bit is set or unset: It is quite easily doable using ‘AND’ operator. Left shift ‘1’ to given position and then ‘AND'(‘&’).

Example:

#include<iostream>

using namespace std;
bool at_position(int num,int pos)
{
bool bit = num & (1<<pos);
return bit;
}
int main()
{
int num = 5;
int pos = 0;
bool bit = at_position(num, pos);
cout << bit << endl;
return 0;
}

Output:

1

Observe that we have first left-shifted ‘1’ and then used ‘AND’ operator to get bit at that position. So if there is ‘1’ at position ‘pos’ in ‘num’, then after ‘AND’ our variable ‘bit’ will store ‘1’ else if there is ‘0’ at position ‘pos’ in the number ‘num’ than after ‘AND’ our variable bit will store ‘0’.

  • Clear all bits from LSB to the ith bit

mask = ~((1 << i+1 ) – 1);
x &= mask;

Logic: To clear all bits from LSB to i-th bit, we have to AND x with mask having LSB to i-th bit 0. To obtain such mask, first left shift 1 i times. Now if we minus 1 from that, all the bits from 0 to i-1 become 1 and remaining bits become 0. Now we can simply take complement of mask to get all first i bits to 0 and remaining to 1.

Example:

x = 29 (00011101) and we want to clear LSB to 3rd bit, total 4 bits
mask -> 1 << 4 -> 16(00010000)
mask -> 16 – 1 -> 15(00001111)
mask -> ~mask -> 11110000
x & mask -> 16 (00010000)

  • Clearing all bits from MSB to i-th bit

mask = (1 << i) – 1;
x &= mask;

Logic: To clear all bits from MSB to i-th bit, we have to AND x with mask having MSB to i-th bit 0. To obtain such mask, first left shift 1 i times. Now if we minus 1 from that, all the bits from 0 to i-1 become 1 and remaining bits become 0.

Example:

x = 215 (11010111) and we want to clear MSB to 4th bit, total 4 bits
mask -> 1 << 4 -> 16(00010000)
mask -> 16 – 1 -> 15(00001111)
x & mask -> 7(00000111)

  • Upper case English alphabet to lower case

ch |= ‘ ‘;

Logic: The bit representation of upper case and lower case English alphabets are:

A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
. .
. .
Z -> 01011010 z -> 01111010

We can set 5th bit of upper case characters, it will be converted into lower case character. Make mask having 5th bit 1 and other 0 (00100000). This mask is a bit representation of the space character (‘ ‘).

Example:

ch = ‘A’ (01000001)
mask = ‘ ‘ (00100000)
ch | mask = ‘a’ (01100001)

  • Lower case English alphabet to upper case

ch &= ‘_’ ;

Logic: The bit representation of upper case and lower case English alphabets are:

A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
. .
. .
Z -> 01011010 z -> 01111010

Clear the 5th bit of lower case characters, it will be converted into upper case character. Make a mask having 5th bit 0 and other 1 (10111111). This mask is a bit representation of the underscore character (‘_’). AND the mask with the character.

Example:
ch = ‘a’ (01100001)
mask = ‘_ ‘ (11011111)
ch & mask = ‘A’ (01000001)

Labels:

Comments

Post a Comment

Popular posts from this blog

Big O Notation — Time & Space Complexity in Ruby!

  Big O Cheat Sheet In this post, we will look at the Big O Notation both time and space complexity! For all our examples we will be using Ruby. What is Big O Notation? Big O notation is just a fancy way of describing how your code’s performance depends on the amount of data its processing. It allows us to calculate the worst possible runtime of an algorithm, or how long it takes the algorithm to complete. In other words, it informs us of how much it will slow down based on the input size. It’s usually talked about in two ways the  time complexity ( how long an algorithm takes )and  space complexity ( how much space an algorithm uses ) Let me put this graph here we can refer to it as we go on, it’s a graph showing the complexities compare against each other. Big O complexity chart Time Complexity Before we get try wrapping our heads around the different big O notations here is a nice table that I am borrowing to show how speed will slow down based on the size of the datas...
Post a Comment
Read more

NT Part 2: Generating Primes, Prime Test, Prime Factorization

  Generating primes fast is very important in some problems. Let's cut to the chase and introduce Eratosthenes's Sieve. The main idea is the following. Suppose we want to find all primes between 2 and 50. Iterate from 2 to 50. We start with 2. Since it is not checked, it is a prime number. Now check all numbers that are multiple of    except  2. Now we move on, to number 3. It's not checked, so it is a prime number. Now check all numbers that are multiple of  ,   except  3. Now move on to 4. We see that this is checked - this is a multiple of 2! So 4 is not a prime. We continue doing this. Here's the implementation. #include <stdio.h> int primechk [ 21000 ] ;   void preprocess ( void ) { int i, j ; for ( i = 2 ; i <= 20000 ; i ++ ) { primechk [ i ] = 1 ; } for ( i = 2 ; i <= 20000 ; i ++ ) { if ( primechk [ i ] == 1 ) { for ( j = 2 ; i * j <= 20000...
Post a Comment
Read more

NT Part 6: Sieve of Eratosthenes(Details)

  About 2300 years ago from today, famous Greek mathematician Euclid proved that there are an infinite number of prime numbers. Since then people have been searching for these prime numbers. In 1849, one of the greatest mathematician of all time, Carl Fredrick Gauss, had identified almost all of the prime numbers within the first 3 hundred thousand whole numbers. In the age of computers, we can find large prime numbers in the blink of an eye. But to do that, we need to know a bit of programming and a 2000 year old algorithm. By the end of this tutorial, you will be able to figure out a solution on your own to Gauss’s problem. What is a Prime Number? A prime number is an integer number that is divisible by 1 and the number itself only. For example, 7 is divisible by 1 and 7 only. But 6 is not a prime number because 6 is be divisible by 2 and 3 as well. It is worth mentioning that 1 itself is not a prime number. Now if you are asked to determine if a number is a prime number, you can...
Post a Comment
Read more