Bits Tricks¶
Java¶
>> (Signed right shift)¶
negative number -> 1 is used as a filler positive number -> 0 is used as a filler
4>>1 -> 2
-4>>1 -> -2
>>> (Unsigned right shift)¶
fills 0
-1 >>> 29 -> 00...0111
-1 >>> 30 -> 00...0011
-1>>>31 -> 00...0001
Detect if two integers have opposite signs¶
XOR¶
bool oppositeSigns(int x, int y)
{
return ((x ^ y) < 0);
}
ternery¶
bool oppositeSigns(int x, int y)
{
return (x < 0)? (y >= 0): (y < 0);
}
32 bit ints¶
bool oppositeSigns(int x, int y)
{
return ((x ^ y) >> 31);
}
Count total set bits in all numbers from 1 to n¶
A simple solution is to run a loop from 1 to n and sum the count of set bits in all numbers from 1 to n.
unsigned int countSetBits(unsigned int n)
{
int bitCount = 0;
for (int i = 1; i <= n; i++)
bitCount += countSetBitsUtil(i);
return bitCount;
}
unsigned int countSetBitsUtil(unsigned int x)
{
if (x <= 0)
return 0;
return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2);
}
Add two numbers without using arithmetic operators¶
iterative¶
int Add(int x, int y)
{
while (y != 0)
{
int carry = x & y;
x = x ^ y;
y = carry << 1;
}
return x;
}
Recursive¶
int Add(int x, int y)
{
if (y == 0)
return x;
else
return Add( x ^ y, (x & y) << 1);
}
Smallest of three integers without comparison operators¶
Method 1 (Repeated Subtraction)¶
int smallest(int x, int y, int z)
{
int c = 0;
while (x && y && z) {
x--;
y--;
z--;
c++;
}
return c;
}
Method 2 (Use Bit Operations)¶
####define CHAR_BIT 8
int min(int x, int y)
{
return y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
}
int smallest(int x, int y, int z)
{
return min(x, min(y, z));
}
Method 3 (Use Division operator)¶
int smallest(int x, int y, int z)
{
if (!(y / x)) // Same as "if (y < x)"
return (!(y / z)) ? y : z;
return (!(x / z)) ? x : z;
}
A Boolean Array Puzzle¶
Input: A array arr[] of two elements having value 0 and 1
Output: Make both elements 0. Specifications: Following are the specifications to follow.
- It is guaranteed that one element is 0 but we do not know its position.
- We can’t say about another element it can be 0 or 1.
- We can only complement array elements, no other operation like and, or, multi, division, …. etc.
- We can’t use if, else and loop constructs.
- Obviously, we can’t directly assign 0 to array elements.
void changeToZero(int a[2])
{
a[ a[1] ] = a[ !a[1] ];
}
void changeToZero(int a[2])
{
a[ !a[0] ] = a[ !a[1] ]
}
void changeToZero(int a[2])
{
a[ a[1] ] = a[ a[0] ]
}
void changeToZero(int a[2])
{
a[0] = a[a[0]];
a[1] = a[0];
}
int main()
{
int a[] = {1, 0};
changeToZero(a);
cout<<"arr[0] = "<<a[0]<<endl;
cout<<" arr[1] = "<<a[1];
return 0;
}