Skip to main content

Bit Manipulation

Basics

  • Computers take instructions in binary, i.e. no or yes, or 0 or 1.

Bit

  • BIT is a short form for Binary digIT
  • A bit is a numeric value representing one of the two states, 0 or 1, no or yes, etc.
  • A bit's states are normally represented as 0 and 1.
  • A 'Set' bit is a bit with value of 1.
  • 'Clearing' a bit means setting its value to 0.

Byte

1 byte = 8 bits
  • A byte is a sequence of 8 bits.
  • Hard Disk and RAM capacities are measured in bytes.
  • A byte can have 2^8 values, ie 256 values, or values from 0 to 2^8-1, or 0 to 255.
  • for an unsigned int, a byte can represent values from 0 to 255.
  • for a signed int, a byte can represent values from -128 to 127.

Basics of Boolean Algebra

  • OR (this or that)
    • symbol is '|'
    • 0 | 0 = 0
    • 0 | 1 = 1
    • 1 | 0 = 1
    • 1 | 1 = 1
  • AND (this and that)
    • symbol is '&'
    • 0 & 0 = 0
    • 0 & 1 = 0
    • 1 & 0 = 0
    • 1 & 1 = 1
  • XOR (Exclusive-OR) (this or that, but not both)
    • symbol is '^'
    • A ^ B will set the bits to 0 where A and B have same bits, and to 1 where the bits are different.
    • 0 ^ 0 = 0
    • 1 ^ 0 = 1
    • 0 ^ 1 = 1
    • 1 ^ 1 = 0
  • Complement (not this)
    • symbol is '~'
    • flips the bits, 0 to 1, and vice versa.
    • ~0 = 1
    • ~1 = 0
  • Left Shift
    • symbol is '<<'
    • x << y means x shifted y bits to the left.
    • If you run out of space, bits drop off from the left.
  • Right Shift
    • symbol is '>>'
    • x >> y means x shifted y bits to the right.
    • If you run out of space, bits drop off from the right.

Additional

  • OR
    • OR is used for setting a bit regardless of the other bit.
    • When you want to set a bit to 1, just 'OR' the bit with 1
    • If x denotes a bit(0 or 1), then the following hold true.
    • x | 0 = x (i.e. OR ing with 0 retains the original bit.)
    • x | 1 = 1 (i.e. OR ing with 1 sets the bit to 1.)
    • ?
      1
      2
      3
      4
      5
      6
      // prints 1
      System.out.println(0 | 1);
      // prints 1
      System.out.println(1 | 1);
  • AND
    • AND can be used for clearing a bit.
    • When you want to 'clear' a bit, just 'AND' it with 0.
    • AND can be used for checking whether a bit is set.
    • To check whether a bit is set, just 'AND' it with 1, it will return whether that bit was set.
    • If x denotes a bit(0 or 1), then the following hold true.
    • x & 0 = 0 (i.e. AND ing with 0 clears the bit to 0)
    • x & 1 = x (i.e. AND ing with 1 retains the original bit)
    • ?
      1
      2
      3
      4
      5
      6
      // prints 0
      System.out.println(0 & 1);
      // prints 1
      System.out.println(1 & 1);
  • XOR
    • for flipping selective bits, XOR is chosen.
    • for flipping a bit, XOR it with 1, it will get reversed.
    • If x denotes a bit(0 or 1), then the following hold true.
    • x ^ 1 = ~x (XOR ing with 1 flips the bits)
    • ?
      1
      2
      3
      4
      5
      6
      // prints 1, because XOR flips the bit.
      System.out.println(0 ^ 1);
      // prints 0, because XOR flips the bit.
      System.out.println(1 ^ 1);
  • NOT
    • The bitwise complement operator, ~, flips every bit in a number.

Usages

  • N << 1 = N*2
  • N << 2 = N*pow(2,2)
  • N << k = N*(pow(2,k))
  • N >> 1 = floor(N/2)
  • N >> 2 = floor(N/pow(2,2))
  • N >> k = floor(N/pow(2,k))
  • N & 1 = last bit in N
  • N & 3 = last 2 bits in N
  • N & 7 = last 3 bits in N
  • N & (pow(2, k)-1) = last k bits in N
  • ~N + 1 = -N
  • N & 0xFF = least significant byte of integer or the last 8 bits of integer.
    • An Integer normally has 4 bytes(32 bits)
    • F in hex is 1111 in binary, so FF(or 0xFF) is 11111111 in binary
    • Doing N & 0xFF removes the first 3 bytes and only keeps the last byte(8 bits) of integer
    • Eg 1783 in binary is 11011110111
    • 1783 & 0xFF only keeps the last 8 bits of 11011110111, and is, 11110111, which is 247

Example Interview Questions

Multiply a no by 2

  • left shift N by 1
  • N << 1
  • ?
    1
    2
    3
    4
    5
    int n = 17;
    // prints 34
    System.out.println(n << 1);

Divide a no by 2

  • right shift N by 1
  • N >> 1
  • ?
    1
    2
    3
    4
    5
    int n = 17;
    // prints 8
    System.out.println(n >> 1);

set the kth bit of N(counting from right) to 1.

  • take 1, shift it k-1 places left, so its at kth place.
  • do 'OR' with N.
  • N = N | (1 << (k-1))
  • ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int n = 17;
    // prints "10001"
    System.out.println(Integer.toBinaryString(n));
    int k = 3;
    // sets the 3rd bit from right to 1;
    n = n | (1 << (k-1));
    // prints "10101";
    System.out.println(Integer.toBinaryString(n));

clear the kth bit of N(counting from right).

  • take 1, shift it k-1 places left, so its at kth place.
  • inverse it, so it becomes 0 and everything else is 1
  • do 'AND' with N.
  • N = N & ~(1 << (k-1))
  • ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int n = 20;
    // prints "10100"
    System.out.println(Integer.toBinaryString(n));
    int k = 3;
    // clears the 3rd bit from right to 0;
    n = n & ~(1 << (k-1));
    // prints "10000";
    System.out.println(Integer.toBinaryString(n));

toggle/flip the kth bit of N(counting from right).

  • Remember the XOR is used for flipping(changing/reversing) the bit
  • take 1, shift it k-1 places left, so it is at kth place.
  • do 'XOR' with N.
  • N = N ^ (1 << (k-1))
  • ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int n = 20;
    // prints "10100"
    System.out.println(Integer.toBinaryString(n));
    int k = 3;
    // toggle the 3rd bit from right;
    n = n ^ (1 << (k-1));
    // prints "10000";
    System.out.println(Integer.toBinaryString(n));

turn off the first set bit(1 bit) of a number N.

  • N-1 will have all bits reversed before and including the first bit set.
  • N & (N-1) will turn off the first set bit.
  • N & (N-1)
  • ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int n = 20;
    // prints "10100"
    System.out.println(Integer.toBinaryString(n));
    // n-1 will have all bits reversed before and including the first bit set
    // n & (n-1) will turn off the first set bit
    n = n & (n-1);
    // prints "10000";
    System.out.println(Integer.toBinaryString(n));

get the count of 1s in a no.

?
1
2
3
4
5
6
7
8
9
10
// Idea: N & 1 gives the first bit.
int count = 0;
while(n > 0) {
    count = count + (N & 1);
    N = N >> 1;
}
return count;
Alternate method: suggested by thevagabond85 in comments.
?
1
2
3
4
5
6
7
8
9
int count = 0;
while(n) {
    n = n & (n-1); // turn off the first set bit(1 bit) of a number N.
    count++;
}
return count;

How to calculate the no of bits to convert from no A to no B.

  • Remember that for flipping a bit, XOR is chosen.
  • A XOR B will give you 1 wherever the bits are different and you need to change bits.
  • now we need to count the no of 1s in C, which is done by above method
  • the result is no of set bits(1 bits) in A ^ B
  • ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    int n1 = 20;
    int n2 = 30;
    // prints "10100"
    System.out.println(Integer.toBinaryString(n1));
    // prints "11110"
    System.out.println(Integer.toBinaryString(n2));
    // n1 ^ n2 will give you 1, wherever the bits are different(you need to change)
    int n = n1 ^ n2 ;
    // count the no of 1s in n, by above method;
    int count = 0;
      
    while(n > 0) {
        count = count + (n & 1);
        n = n >> 1;
    }
    // prints 2,
    // two bits required to change from 10100 to 11110
    System.out.println(count);

Check if N is a power of 2 or not.

  • if N is a power of 2, it will have only one 1, and rest all 0s.
  • if N is a power of 2, N-1 will have all 1s, except that the 1 bit of N will be converted to 0.
  • so, if N is a power of 2, then (N & (N-1) == 0)
  • ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int n1 = 20;
    int n2 = 32;
    // n = power of 2 will have one 1 followed by all 0s.
    // n-1 will have one 0 followed by all 1s.
    // n & (n-1) is 0 for power of 2, and 1 otherwise.
    // prints false, becase 20 is not a power of 2.
    System.out.println((n1 & (n1-1)) == 0);
    // prints true, because 32 is a power of 2.
    System.out.println((n2 & (n2-1)) == 0);

Check if N is a power of 4 or not.

  • check that N is a power of 2(from above)
  • check that there are a total of even 0s in the binary representation of N.

How to get the last 3 bits of an integer.

  • we just do AND with 111.
  • N & ((1 << 3)-1)
  • ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int n = 22;
    int k = 3;
    // prints "10110"
    System.out.println(Integer.toBinaryString(n));
    // take 1, shift it k digits left, and subtract 1,
    // so that k 1s are left, 1111...k times.
    // now do, AND with n, it will give last k digits of n
    n = n & ((1 << k) - 1);
    // prints "110", last 3 digits of "10110"
    System.out.println(Integer.toBinaryString(n));

Get the 5 highest bits of an integer(8 bit integer).

  • for getting the 5 highest bits, we will remove the lower 3 bits and do 'AND' with 11111.
  • we create 11111 by left shifting 1 by 5, 1 << 5, which gives 100000, and subtracting 1, which gives 11111.
  • so we create 11111 by (1 << 5)-1
  • we remove the lower 3 bits of x by (x >> 3)
  • Doing 'AND' gives us the final answer.
  • (x >> 3) & ((1 << 5)-1)

check whether the kth bit in N is 1.

  • take 1, shift 1 by k-1 to the left, (1 << (k-1))
  • Do N AND above, ie N & (1 << (k-1))
  • The above result will have all digits 0, except the most significanr digit, which will be 0 if the nth bit in x is 0.
  • So, if the nth significant bit in x is 0, then expression x & (1 << (n-1)) will be 0.
  • So, if the nth significant bit in x is 1, then expression x & (1 << (n-1)) will not be 0.
  • N & (1 << (k-1)) != 0

swap two nos using bitwise operations.

  • A = A ^ B
  • B = A ^ B
  • A = A ^ B
  • Note that (A ^ B) ^ B => (flips every bit of 'A' twice or zero times, essentially which means gives back 'B').
  • Note that (A ^ B) ^ ((A ^ B) ^ B) => (A ^ B) ^ A => B => (flips every bit of 'B' twice, essentially giving back 'B')

swap even and odd bits in a no(4 byte integer)

  • (N & 0xaaaaaaaa) gives the even bits(because a is 1010, so aa is 10101010, doing & with N, gives the even bits)
  • (N & 0x55555555) gives the odd bits(because 5 is 0101, so 55 is 01010101, doing & with N, gives the odd bits)
  • (N & 0xaaaaaaaa) >> 1 shifts even to odd bits
  • (N & 0x55555555) << 1 shifts odd bits to even bits.
  • ((N & 0xaaaaaaaa) >> 1) | ((N & 0x5555555555) << 1) gives us the required no where even and odd bits are swapped.

Misc



  • IP address
    • normally represented as A:B:C:D
    • has 4 bytes, each of A, B, C, D representing a byte(8 bits).
    • each of A, B, C, D is 1 byte or 8 bits, and can have values from 0 to 255
  • Right most bit(assuming 16 bit integer)???
    • N & 0xff;
  • Left most bit(assuming 16 bit integer)???
    • (N>>8) & 0xff;
  • Sign bit(assuming 16 bit integer)???
    • N & 0x8000;


Binary representation of a given number

void bin(unsigned n)
{
    unsigned i;
    for (i = 1 << 31; i > 0; i = i / 2)
        (n & i)? printf("1"): printf("0");
}




void bin(unsigned n)
{
    if (n > 1)
        bin(n/2);
    printf("%d", n % 2);
}



Check if binary representation of a number is palindrome


int x = 1<<31 + 1;    // Let us take x be 1000000000001
int h_byte = (x & 0xffff0000) >> 16 ;
int l_byte = (x & 0x0000ffff) << 16;
int y;
y = l_byte | h_byte;
if(x == y) {
cout<<"palindrome!!";
}

XOR Approach:

(Assuming 32 bit int as an input)
int a = num & 0xFFFF0000;
int b = num & 0x0000FFFF;
if (a ^ b == 0) then palindrome, otherwise not.


Detect if two integers have opposite signs

bool oppositeSigns(int x, int y)
{
    return ((x ^ y) < 0);
}




bool oppositeSigns(int x, int y)
{
    return ((x ^ y) >> 31);
}


 Function to find minimum of x and y


int min(int x, int y)
{
  return  y + ((x - y) & ((x - y) >>
            (sizeof(int) * CHAR_BIT - 1)));


}


Rotate bits of a number


n -> number , d->digits

left rotate  ::  (n << d)|(n >> (INT_BITS - d)

right rotate :: (n >> d)|(n << (INT_BITS - d))

Round up to the next highest power of 2

unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;



Let us try for 17(10001)
    step 1
       n = n - 1 = 16 (10000)  
    step 2
       n = n | n >> 1
       n = 10000 | 01000
       n = 11000
       n = n | n >> 2
       n = 11000 | 00110
       n = 11110
       n = n | n >> 4
       n = 11110 | 00001
       n = 11111
       n = n | n >> 8
       n = 11111 | 00000
       n = 11111
       n = n | n >> 16
       n = 11110 | 00000
       n = 11111    

    step 3: Return n+1
     We get n + 1 as 100000 (32)


Function __builtin_clz

This builtin method is provided by GCC to count the number of leading zero’s in variable. The Syntax:
Code:
int __builtin_clz (unsigned int x)
It takes the input parameter as a number for which the the count of leading zero’s is to be determined. It returns the count of leading zero’s as expected.  Taking for example, lets take a number 16. An int takes 4 bytes in gcc. Its binary representation is 
Code:
00000000 00000000 00000000 00010000
Counting the number of leading zero’s is 27 which should be our result for this case..

Function __builtin_ctz

This builtin method by GCC determines the count of trailing zero in the binary representation of a number. The Syntax:
Code:
int __builtin_ctz (unsigned int x)
The input parameter is the number for which the the count of trailing zero’s is to be determined. It returns the count of trailing zero’s as expected.  Taking for example, lets take the same number 16. Again, an int takes 4 bytes in gcc. Its binary representation is 
Code:
00000000 00000000 00000000 00010000
Counting the number of trailing zero’s is 4 which should be our result for this case..

Function __builtin_popcount

This builtin method by GCC determines the number of one’s in the binary representation of a number. The Syntax:
Code:
int __builtin_popcount (unsigned int x)
The input parameter is the number for which the the number of 1’s is to be determined. It returns the count of set bits as expected..  Taking for example, lets take the same number 16. Again, an int takes 4 bytes in gcc. Its binary representation is 
Code:
00000000 00000000 00000000 00010000
Counting the number of one’s is just 1, which should be our result for this case..

Complete Example

Here is a complete example program which demonstrates the use of these builtin methods.
Code:
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int num = 16;
    int clz = 0;
    int ctz = 0; 
    int ones = 0;

    clz = __builtin_clz(num);
    printf("Number of leading zero's in %d is %d\n", num, clz);  

    clz = __builtin_clz(-num);
    printf("Number of leading zero's in %d is %d\n", -num, clz);  

    ctz = __builtin_ctz(num);  
    printf("Number of trailing zero's in %d is %d\n", num, ctz);

    ones = __builtin_popcount(num);  
    printf("Number of one's in %d is %d\n", num, ones);    

    return 0;
}
On running the above example program, here is our output:
Code:
Number of leading zero's in 16 is 27
Number of leading zero's in -16 is 0
Number of trailing zero's in 16 is 4
Number of one's in 16 is 1
Great! it works fine as per our understanding. Note, it even worked fine for negative numbers which are stored as two’s complement.


Code to find the Greatest Common Divisor of two numbers.

int GCD(int a,int b) { while(b^=a^=b^=a%=b); return a; }



Compute the integer absolute value (abs) without branching.


 int v; // we want to find the absolute value of v unsigned
 int r;  // the result goes here 

 int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

Compute the minimum (min) or maximum (max) of two integers without branching.

 int x; // we want to find the minimum of x and y 
 int y; 
 int r;  // the result goes here 

 r = y ^ ((x ^ y) & -(x < y)); // min(x, y) 

 r = x ^ ((x ^ y) & -(x < y)); // max(x, y)




Reversing a bits in an integer:

x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);

Counting number of bits:

while(n) {
    n = n & (n-1);
    count++;
}
return count;


Upper Case into Lower Case


"CAPITAL LETTER" XOR " " = "small letter"
 "W" XOR " " = "w"
 "g" XOR " " = "G"






Comments

Popular posts from this blog

ORACLE 9i practice solutions

Created by BCL easyConverter SDK 3 (HTML Version)

Hackerrank > SQL > Basic Select

Select
01-Select All
Given a City table, whose fields are described as +-------------+----------+ | Field       | Type     | +-------------+----------+ | ID          | int(11)  | | Name        | char(35) | | CountryCode | char(3)  | | District    | char(20) | | Population  | int(11)  | +-------------+----------+
write a query that will fetch all columns for every row in the table.

My Solution
SELECT*FROM city;
---------------------------------------------------------------------------------
02-Select by ID
Given a City table, whose fields are described as

Zoho Interview | Set 1 (Advanced Programming Round)

Third Round: (Advanced Programming Round) Here they asked us to create a “Railway reservation system” and gave us 4 modules. The modules were:
    1. Booking
    2. Availability checking
    3. Cancellation
    4. Prepare chart
We were asked to create the modules for representing each data first and to continue with the implementation phase.

 My Solution :

#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<time.h>#include<iomanip.h>#include<fstream.h>char f[10]="f";char s[10]="s";int addr,ad,flag,f1,d,m,i,amt;float tamt; class login {public:char id[100];char pass[100];char*password;void getid(){ cout<<"Enter your id:";gets(id); password=getpass("Enter the password:");strcpy(pass,password);}void displayid(){ cout<<"Id:";puts(id); cout<<"Password:";puts(pass);}}; class detail {public:in…