Bitwise operators in most of the programming languages are common and inherited from the C (e.g.: &, |, ^, >>, …). These operations are critical in the low-level programming (for instance for writing drivers).
In the beginning of this post I’ll just briefly pass over them and present some tricks using them. As a programming language choice, I’ll give examples from C and python.
See the resources for more complete and detailed overview.
Two most Fundamental Bitwise operators
There are two types of conditional operator in most of the programming languages, logical one the bitwise one. For example “bitwise AND” is shown as “&” and the “logical AND” is shown with “&&”. Similarly “bitwise OR” is | and “logical OR” is “||”.
AND operator
Bitwise AND (&) is very similar to the “logical AND” but instead it works with bits only. The bitwise AND compares each bit of the first operand to the corresponding bit of the second operand. It returns 1 if and only if both of its operands are equal to 1, otherwise it returns 0.
For example 00&11 is 0.
Let’s fire up python shell and write 5&7 the result is 5 but how?
5 in binary format is 0101 and 7 is 0111 and by comparing each bit we’ll get 0101 which is 5.
We can use this notion for detecting if a bit is 0 or 1.
For example, given a bit pattern: 0011 (decimal 3), we can determine whether the second bit is 1 may be done by using a bitwise AND with a bit pattern containing 1 only in that bit:
0011 (decimal 3)
& 0010 (decimal 2)
--------------------
= 0010 (decimal 2)
Because the result 0010 is non-zero, we know the second bit in the original pattern was 1. This process is usually called as bit masking.
OR operator
A bitwise OR (|) takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. For each pair, if either bit is 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0.
For example if calculate 5&7 in python you’ll get 7. Because 5 in binary format is 0101 and 7 is 0111 and by comparing each bit with inclusive OR we’ll get 0111 which is 7.
The bitwise OR may be used to set selected bits. One example is to set a specific bit (or flag) in a register where each bit represents an individual Boolean state. For example: 0010 (decimal 2) can be considered a set of four flags. The first, second, and fourth flags are clear (0), while the third flag is set (1). The first flag may be set by performing a bitwise OR between this value and a bit pattern in which the first flag is set:
0010 (decimal 2 )
| 1000 (decimal 8 )
--------------------
= 1010 (decimal 10 )
This technique is an efficient way to deal with a number of Boolean values using the minimum of memory.
Other important bitwise operators
NOT
The bitwise NOT (~), or complement, is a unary operation that performs logical negation on each bit, forming the ones’ complement of the given binary value. Digits which were 0 become 1, and vice versa. For example:
~7 is 8. Because 7 in binary format is 0111 and by converting each bit we’ll get 1000 which is 8.
If the number is signed we’ll use two’s complement for the bitwise not operator.
XOR
The term bitwise XOR (^) stands for “exclusive OR,” and means “one or the other, but not both.” In other words, XOR compares each bit, returns 1 if and only if exactly one of its operands is 1. If both operands are 0, or both are 1, then XOR returns 0. For example:
0101 (decimal 5)
^ 0011 (decimal 3)
--------------------
= 0110 (decimal 6)
Assembly language programmers sometimes use the XOR operation as a short-cut to set the value of a register to zero. Performing XOR on a value against itself always yields zero, and on many architectures this operation requires fewer CPU clock cycles and/or fewer bytes (less precious cache-space) than loading a zero value and saving it to the register.
The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip). Given the bit pattern: 0010 (decimal 2) the first and third bits may be toggled simultaneously by a bitwise XOR with a bit pattern containing 1 in the first and third positions:
0010 (decimal 2 )
^ 1010 (decimal 10 )
---------------------
= 1000 (decimal 8 )
This technique also may be used to manipulate bit patterns representing sets of Boolean states.
Bitwise shifts
There are two bitwise shift operators and they are shift left and shift right. In C, these are represented by the << and >> operators, respectively. These operations are very simple, and do exactly what they say: shift bits to the left or to the right. The syntax for a shift operation is as follows:
[integer] [operator] [number of places]
A statement of this form shifts the bits in [integer] by the number of places indicated, in the direction specified by the operator.
Left Shift
Left shift basically shifts the binary n bits to the left. A left arithmetic shift by n is equivalent to multiplying by 2^n (provided the value does not overflow). For example:
Fire up your python shell and run the following in the shell:
3 << 2
Result of this operation is 12. Because,
Decimal 3 is 0011 in binary. When you shift 0011 2 bits to the left, you'll get 1100 and that's 12.
Another example is:
x = 0000 1010 1000 0001;
x = x << 4;
After shifting 4 bits, the new x will be:
1010 1000 0001 0000
Every bit is shifted to the left by one place. When you do this, the MSB (most significant bit, remember?) of x is lost, because there isn't another place to shift it to. Similarly, after a shift left, the LSB of x will always be 0. There is no position to the right of the LSB, and so there's nothing to shift into the LSB, so it's assigned a value of 0.
Right Shift
Similar to the left shift, right shift basically shifts the binary number n bits to the left. That's actually taking two's complement of the number or dividing by 2^n. An example is:
12>>2
and result of this is 3. Because 12 in binary is 1100 and when you shift two bits you'll get 0011 which is 3.
Another example is,
x = 0110 1111 1001 0001;
x = x >> 4;
and the x in the end will be 0000 0110 1111 1001. Here, the bits are being shifted right by four places.
Some Hacks
Computing the modulus:
If the divisor is a power of 2, the modulo (%) operation can be done with:
modulus = numerator & (divisor - 1);
This is about 600% faster.
x = 131 % 4;
//equals:
x = 131 & (4 - 1);
Absolute Value
Forget Math.abs() for time critical code. Version 1 is 2500% faster than Math.abs(), and the funky bitwise version 2 is again 20% faster than version 1.
//version 1
i = x < 0 ? -x : x;
//version 2
i = (x ^ (x >> 31)) - (x >> 31);
Swap integers without a temporary variable using XOR
That's a pretty neat trick and this is about 20% faster.
int a, b, t;
a = b;
b = t;
//equals:
a ^= b;
b ^= a;
a ^= b;
Multiplication
Here is a bitwise multiplication algorithm only using bitwise shifts and addition.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <stdio.h>
int multiply (int a, int b){
int c = 0;
while (b!=0) {
if ((b & 1) != 0)
c = c + a;
a = a<<1;
b = b>>1;
}
return c;
}
int main () {
int a = 3, b = 8, c, d;
c = multiply(a, b);
d = a * b;
if (c == d) {
printf("Result is %d\n", c);
}
else {
printf("Incorrect : %d\n", c);
}
return 0;
} |
Detect if two integers have opposite signs
int x, y; // input values to compare signs
bool f = ((x ^ y) < 0); // true iff x and y have opposite signs
Check if an integer is even/uneven using bitwise AND
isEven = (x & 1) ^ ((-1 & 1) | ((x < 0) ? 0 : 1)));
This example is taken from this SO post.
Compute the minimum (min) or maximum (max) of two integers without branching
This one is from Bit Twiddling Hacks page:
If you know that INT_MIN <= x - y <= INT_MAX, then you can use the following, which are faster because (x - y) only needs to be evaluated once.
r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)
r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)
Note that the 1989 ANSI C specification doesn't specify the result of signed right-shift, so these aren't portable. If exceptions are thrown on overflows, then the values of x and y should be unsigned or cast to unsigned for the subtractions to avoid unnecessarily throwing an exception, however the right-shift needs a signed operand to produce all one bits when negative, so cast to signed there.
Sign Flipping
Sign flipping using NOT or XOR:
i = -i;
//equals
i = ~i + 1;
//or
i = (i ^ -1) + 1;
Useful Resources
Bitwise Tricks
Bitwise Operations in C
The art of Programming Fasc 1
Bitwise gems – fast integer math
Bit Twiddling Hacks
Bitwise Operations
Reciprocal Multiplication, a tutorial
Related Posts:
![[a,b]](http://mathworld.wolfram.com/images/equations/RiemannSum/Inline1.gif){kind=small}
be partitioned by points 
, where the lengths of the resulting intervals between the points are denoted 
, 
, …, 
. Let 
be an arbitrary point in the 
th subinterval. Then the quantity
and partition, and the value 
is called the 
, this limit is known as the Riemann integral of 
over the interval ![[a,b]](http://mathworld.wolfram.com/images/equations/RiemannSum/Inline12.gif){kind=small}
. The shaded areas in the above plots show the 
.
Recent Comments