In opposite to left shift, when we right shift a number we divide it by a power of two. For example, 4 » 2 = 0100 » 2 = 0001 = 1 = 4 / 2^2. Here is the general formula:
a >> b = a / 2^b
Multiply a number by a power of two using bit left shift
Remember the bit shift operation? « and »? Well if we left shift a number, we are multiplying that number by a power of two. For example, 1 = 0001. If we left shift it by 1, we’ll have 1 « 1 = 0010 = 2 = 1 * 2^1. If we left shift it by 2, we’ll have 1 « 2 = 0100 = 4 = 1 * 2^2. Thus, the general formula is:
[Read More]
Turning a bit off without affecting other bits
Hello and welcome to the second part of “Bit Manipulation Tips & Tricks.” If you haven’t read the first part yet, here is the link of you. Read it! :)
1. Turning a bit off without affecting other bits
Turning a bit off means to change 1 bits (on) to 0 bits (off) and if the bits are already off then they’ll stay off. This can be accomplished by using the ~, « and & operators.
[Read More]
Bit Manipulation Tips and Tricks
In this series, we’ll try to compile a list of tips and tricks that are useful for performing bitwise operation.
Multiply a number by a power of two using bit left shift
Divide a number by a power of two using bit right shift
Toggle a specified bit in a bit string without effecting other bits
Checking if a bit is on or off without affecting other bits
Turning a bit off without affecting other bits
[Read More]
Finding an integer that repeats odd number of times in an array of positive integers
Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity?
Solutions
Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0.
[Read More]
Check If an Integer's Bit Representation Is a Palindrome
Question: how can you determine if a positive integer is a palindrome. For example, 5 is a palindrome because 5 = 101. Also, 9 is a palindrome because 9 = 1001.
Solution: an integer is palindrome when its bit representation is the same reading from left to right or from right to left. Thus, in order to know if it is a palindrome or not, we just have to check if the number’s value is still the same when we read the number’s bits backward (right to left).
[Read More]
Implement Add,Subtract,Multiplication,Division Using Bit Manipulation
Addition
This One is Somewhat Logical and the Best also. This will work all kind of Inputs. The Logic Behind the Concept is described breifly here :
Here we use, One’s Complement Operator (~ - Known as Tilda). This is a Unary Operator. The output of “~b” means, One Complement of the value stored in ‘b’. For example, a=10, b=5. Then the ~b=-6. This operator simply works on the binary value of the corresponding Integer.
[Read More]
Reverse a String using bits
Question: Reverse a string in C using as little additional memory as possible.
Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code.
Method 1 - Normal Reversal of String
void reverseString(char\* str) { int i, j; char temp; i\=j\=temp\=0; j\=strlen(str)\-1; for (i\=0; i<j; i++, j\-\-) { temp\=str\[i\]; str\[i\]\=str\[j\]; str\[j\]\=temp; } } Method 2 - Using xor to swap 2 characters
[Read More]
Give a fast way to multiply a number by 7
Multiply by 8 (left shift by 3 bits) and then subtract the number.
(x << 3) - x
To reverse the bits in an integer
Method1
`
unsigned int num; // Reverse the bits in this number.
unsigned int temp = num; // temp will have the reversed bits of num.
int i;
for (i = (sizeof(num)*8-1); i; i–)
{
temp = temp | (num & 1);
temp «= 1;
num »= 1;
}
temp = temp | (num & 1);
`
Method2
In this method, we use a lookup table.
`
const unsigned char ReverseLookupTable[] =
[Read More]