Multiply by 2
Given a number x:
if (x % 2 == 0) => true
Method 2:
Given a number x:
if ( x & 1) => false
Method 3:
Given a number x:
if ( x & (x-1)) => true
logic here is that in case of number 1 less than the even number, all the lower order bits would get set
Find the lowest bit set of a given number:
Method 1:
Given a number x:
x & -x gives the lowest bit set
Finding a complement of a number/reversing the bits in a given number:
Method 1:
Given a number x:
~x gives the complement of x i.e. set bits becomes unset and vice-versa
Method 2:
Given a number x:
-x == ~x + 1
so ~x == -x -1
so another way of expressing would be -(x + 1)
Method 3:
Given a number x:
XOR operation can be used to reverse the set bits.
x ^ ~0 where ~0 sets all the bit to 1
Adding 2 numbers
Method 1:
Given 2 numbers x and y:
x + y <==> (x & y) + (x | y)
Finding the maximum between 2 numbers:
Method 1:
Given 2 numbers x and y:
max = y;
if ( x > y)
max = x;
Method 2:
importance of x ^ y ^ z
if ( z == x ) then x ^ y ^ x returns y
Swapping 2 numbers:
Method 1:
Given 2 numbers x and y:
swap (int x , int y)
{
int temp = x;
x = y;
y = x;
}
Method 2:
Given 2 numbers x and y:
swap (int x, int y)
{
x ^= y;
y ^= x;
x ^= y;
}
Bit interleaving:
Method 1:
Given 2 numbers x and y, interleave the bits in z such that the bits in x form the odd and that of y in even position
for ( i = 0; i < 8 * sizeof (i); i++)
{
z |= ( ( x & (1U << i) ) << i ) | ( ( y & (1U << i) ) << (i + 1) )
}
Determine the sign of a number:
-1 if x < 0
+1 if x > 0
0 if x = 0
Method 1:
Given a number x:
s8 sign_num (s32 x)
{
return (x > 0 + x < 0);
}
Method 2:
Given a number x:
(x >> 32) results in -1 or 0 depending on whether x is signed or unsigned number respectively.
(x >> 32) || ( (u32)(-x) >> 32 )
Returning the absolute value of a integer number:
Method 1:
Giver a number x:
int abs_val(int x)
{
return x > 0:x ? -x;
}
Method 2:
Given a number x:
int abs_val (int x)
{
int int_type = x >> 32; // -1 for signed and 0 for unsigned types
return (x ^ int_type) - int_type;
}
setting a bit at a particular position:
Method 1:
Given a number x and bit to be set @ position pos
int set_pos (int pos, int &x)
{
return x | (1 << pos);
}
unsetting a bit at a particular position:
Method 1:
Given a number x and bit to be unset @ position pos
int set_pos (int pos, int &x)
{
return x & ~(1<< pos);
}
Flipping bit at a particular position:
Method 1:
Given a number x and bit to be flipped is @ position pos
int flip_pos (int pos, int &x)
{
return x ^ (1 << pos);
}
Check whether the bit at a particular position is set:
Method 1:
Given a number x and bit state to be determined @ position pos
int state_pos(int pos, int &x)
{
return x & ( 1 << pos);
}
Modify a particular bit at a particular position:
Method 1:
Given a number x and bit state to be changed @ position pos
int modify_bit(int pos, int &x, bool val_to_set)
{
return ( x & ~(1 << pos) ) | ( (-1) & (1 << pos) );
}
Unset the rightmost set bit
Method 1:
Given a number x
(x & x -1) turns the 1st rightmost bit off.
Determine whether a given number is of the form 2 pow n -1
Method 1:
Given a number x:
(x & (x + 1)) returns 0 if true
Extract the rightmost 1st set bit of a given number x
Method 1:
Given a number x:
x & -x returns either 0 or rightmost set bit
Method 1: x * 2
Method 2: x << 2
Dividing by 2
Dividing by 2
Method 1: x / 2
Method 2: x >> 2
*Same way multiplication and division operation can be carried out for numbers by shifting. This
operation is applicable if we need a even multiple
Find whether the number is multiple of 4
A number is multiple of 4, if the last 2 digits of the number is divisible by 4.
To be noted: The bit pattern representation of 4 is 100 i.e. the last 2 bits are 0.
It can be another way to find the divisibility
It can be another way to find the divisibility
Given a number x: if (x % 4 == 0) => divisible by 4
x: if (x ^ 3 == 3) => divisible by 4
Round off a number to a nearest number divisible by 4
Possible values on dividing a number by 4 is 0,1,2,3.
Method 1:
Given a number x:
y = x % 4;
switch (y)
{
case 0:
return x;
case 1:
case 2:
return x - y;
case 3:
return x + 1;
}
Method 2:
Given a number x:
switch ( x & 3)
{
case 0:
return x;
case 3:
return x++;
case 1:
case 2:
return x -= (x & 2) + ( x & 1);
}
Method 3:
Given a number x:
x = (( x & 3 ) && (x + 1) ) || (x & ~3);
Find whether a given number is a multiple of 2 / a number an even number
Method 1:Given a number x:
if (x % 2 == 0) => true
Method 2:
Given a number x:
if ( x & 1) => false
Method 3:
Given a number x:
if ( x & (x-1)) => true
logic here is that in case of number 1 less than the even number, all the lower order bits would get set
Find the lowest bit set of a given number:
Method 1:
Given a number x:
x & -x gives the lowest bit set
Finding a complement of a number/reversing the bits in a given number:
Method 1:
Given a number x:
~x gives the complement of x i.e. set bits becomes unset and vice-versa
Method 2:
Given a number x:
-x == ~x + 1
so ~x == -x -1
so another way of expressing would be -(x + 1)
Method 3:
Given a number x:
XOR operation can be used to reverse the set bits.
x ^ ~0 where ~0 sets all the bit to 1
Adding 2 numbers
Method 1:
Given 2 numbers x and y:
x + y <==> (x & y) + (x | y)
Finding the maximum between 2 numbers:
Method 1:
Given 2 numbers x and y:
max = y;
if ( x > y)
max = x;
Method 2:
Given 2 numbers x and y:
max(x, y) == x + ((y - x) & -(x < y))importance of x ^ y ^ z
if ( z == x ) then x ^ y ^ x returns y
Swapping 2 numbers:
Method 1:
Given 2 numbers x and y:
swap (int x , int y)
{
int temp = x;
x = y;
y = x;
}
Method 2:
Given 2 numbers x and y:
swap (int x, int y)
{
x ^= y;
y ^= x;
x ^= y;
}
Bit interleaving:
Method 1:
Given 2 numbers x and y, interleave the bits in z such that the bits in x form the odd and that of y in even position
for ( i = 0; i < 8 * sizeof (i); i++)
{
z |= ( ( x & (1U << i) ) << i ) | ( ( y & (1U << i) ) << (i + 1) )
}
Determine the sign of a number:
-1 if x < 0
+1 if x > 0
0 if x = 0
Method 1:
Given a number x:
s8 sign_num (s32 x)
{
return (x > 0 + x < 0);
}
Method 2:
Given a number x:
(x >> 32) results in -1 or 0 depending on whether x is signed or unsigned number respectively.
(x >> 32) || ( (u32)(-x) >> 32 )
Returning the absolute value of a integer number:
Method 1:
Giver a number x:
int abs_val(int x)
{
return x > 0:x ? -x;
}
Method 2:
Given a number x:
int abs_val (int x)
{
int int_type = x >> 32; // -1 for signed and 0 for unsigned types
return (x ^ int_type) - int_type;
}
setting a bit at a particular position:
Method 1:
Given a number x and bit to be set @ position pos
int set_pos (int pos, int &x)
{
return x | (1 << pos);
}
unsetting a bit at a particular position:
Method 1:
Given a number x and bit to be unset @ position pos
int set_pos (int pos, int &x)
{
return x & ~(1<< pos);
}
Flipping bit at a particular position:
Method 1:
Given a number x and bit to be flipped is @ position pos
int flip_pos (int pos, int &x)
{
return x ^ (1 << pos);
}
Check whether the bit at a particular position is set:
Method 1:
Given a number x and bit state to be determined @ position pos
int state_pos(int pos, int &x)
{
return x & ( 1 << pos);
}
Modify a particular bit at a particular position:
Method 1:
Given a number x and bit state to be changed @ position pos
int modify_bit(int pos, int &x, bool val_to_set)
{
return ( x & ~(1 << pos) ) | ( (-1) & (1 << pos) );
}
Unset the rightmost set bit
Method 1:
Given a number x
(x & x -1) turns the 1st rightmost bit off.
Determine whether a given number is of the form 2 pow n -1
Method 1:
Given a number x:
(x & (x + 1)) returns 0 if true
Extract the rightmost 1st set bit of a given number x
Method 1:
Given a number x:
x & -x returns either 0 or rightmost set bit
Extract the rightmost 1st 0 set bit of a given number x
Method 1:
Given a number x:
-x & (x + 1) returns either 0 or rightmost set bit
