We all familiar with calculation operators like * / % . But when we are facing operators like ^ | & ~ , what do they mean? In fact, these operators are doing the binary calculation on numbers. In ruby, it’s simple to translate a number between its binary representation using num.to_s(2), string.to_i(2) , for example: 8.to_s(2) = "1000", "1000".to_i(2) = 8. In this post, I’ll introduce the bitwise operators’ meanings and manipulations.
Operators meaning and symbol
+----------+----------------+
| Symbol | Meaning |
|----------|----------------|
| & | and |
|----------|----------------|
| | | or |
|----------|----------------|
| ^ | XOR |
|----------|----------------|
| ~ | not |
|----------|----------------|
| >> | left shift |
|----------|----------------|
| << | right shift |
+----------+----------------+And operator:
The bitwise and operator is applying logic and(&&) to binary representations of two numbers. The rule is return 1 if both bits are 1, otherwise, return 0.
18 & 26 => 18 |
Explain: | 10010
18.to_s(2) => "10010" | & 11010
26.to_s(2) => "11010" | --------
| 10010
10010 is the binary representation of 18.Manipulation:
It’s obvious that for a given number x, x & x = x, x & 0s = 0, x & 1s = x . Based on this characteristic, we can reduce the running time in some calculation problems.
To determine whether a number is the power of two, my first intuition is to create a while loop to divide 2 each time. However, this problem can be easily solved by bit manipulation using the bitwise and operator. As we know, binary numbers that representing the power of two has a leading 1, then followed by all zeros.
1 => 1, 2 => 10, 4 => 100, 8 => 1000, ... , 1024 => 10000000000
However, the binary representation of n - 1 is following a totally opposite path:
3 => 11, 7 => 111, ... , 1024 => 1111111111
Following the rule of bitwise and operator, if a number n is the power of two, n & (n-1) = 0 .
#iterative solution running time is O(log(n)):
def is_power_of_two(n)
return false if n == 0
while n % 2 == 0 do
n /= 2
end
n == 1
end#bit manipulation, running time is O(1):
def is_power_of_two(n)
return n > 0 && (n & (n - 1)) == 0
end
Or operator:
Similar to logic or(||) operator, bitwise or will return 1 if at least one of the bits is 1.
18 | 26 => 26
Explain: | 10010
18.to_s(2) => "10010" | | 11010
26.to_s(2) => "11010" | --------
| 11010
11010 is the binary representation of 26.Manipulation:
The property of or operator is similar to bitwise and, it can be applied to some calculation problems. Following the rules: x | x = x, x | 0s = x, x & 1s = 1s .
XOR operator:
The bitwise XOR operator is also called exclusive OR operator. When doing XOR on two binary numbers, return 0 if both bits are the same(1 or 0), return 1 if one of the bits is 1 and the other bit is 0.
18 ^ 26 => 8 |
Explain: | 10010
18.to_s(2) => "10010" | ^ 11010
26.to_s(2) => "11010" | --------
| 01000
1000 is the binary representation of 8.Manipulation:
The properties of the XOR operator on two number are: x ^ 0s = x, x ^ 1s = ~x, x ^ x = 0 . Besides calculation problems, the XOR operator can also be applied to find the target number in an array:
This problem has many solutions. For example, we could have a hash to store the number and its appearance, then return the number with appearance == 1. However, a hash will cost extra O(n/2) space. We could reduce the space complexity to constant by applying XOR operation. As we know x ^ x = 0 , while we iterate the array, and doing XOR operation on each number, all the duplicates number in this array will cause the result = 0 . Since x ^ 0 = x , result is the single number in this array.
#given nums = [2,2,4,5,4,1,1]
#result = 0 ^ 2 ^ 2 ^ 4 ^ 5 ^ 4 ^ 1 ^ 1
# = 0 ^ (2 ^ 2) ^ (4 ^ 4) ^ (1 ^ 1) ^ 5
# = 0 ^ 0 ^ 0 ^ 0 ^ 5
# = 5def single_number(nums)
result = 0
nums.each do |num|
result ^= num
end
result
end
Not operator:
Similar to the logic not(!) operator, the bitwise not operator is negating every bit in a number’s binary representation: return 1 if the current bit is 0, return 0 if the current bit is 1. Different from the bitwise and and bitwise or operators which are applied to two numbers, the bitwise not operator can only be applied to a single number. What’s more, bitwise not operator is using two’s complement in translating negative nums to binary numbers.
~26 => -27 |
Explain: |
26.to_s(2) => "11010" | ~ 11010
| --------
| 00101
Integer 27 in binary representation: 11011
Applying two's complement, -27 is 00101, which is the same as ~26Manipulation:
The bitwise not operator is openly used in finding the last 1’s position in a number by doing n&(~n)
180.to_s(2) => "10110100" | 10110100
~180 => 01001100 | & 01001100
| ------------
00000100
The last 1 occurs at index 5.Left & right shift operator:
The bitwise left and right shift operators are shifting bits to left or right with a given number.
18 >> 2 => 4 |
Explain: |
18.to_s(2) => "10010" | 10010
| >> 2
| --------
| 100
100 is the binary representation of 4 18 << 2 => 72 |
Explain: |
18.to_s(2) => "10010" | 10010
| << 2
| --------
| 1001000
1001000 is the binary representation of 72
Manipulation:
Bitwise shift operator can be used in translating a decimal number to a number in base 4n. For example, this problem is asking to translate a decimal number to its hexadecimal representation:
Since 2⁴ = 16. We can translate the number by iterating it’s bits by a group of 4 each time. After translating each group, we left shift to the next group of 4 bits.
def to_hex(num)
map = {0 => '0',1 => '1',2 => '2',3 => '3',4 => '4',5 => '5',6 => '6',7 => '7',8 => '8',9 => '9',10 => 'a',11 => 'b',12 => 'c',13 => 'd',14 => 'e',15 => 'f'} return '0' if num == 0
result = ''
while num != 0 && result.size < 8 do
result = map[(num & 15)] + result
num = num >> 4
end
result
end
