# Bitwise operators: definition and manipulation in Ruby

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.

`                  +----------+----------------+                  |  Symbol  |    Meaning     |                  |----------|----------------|                  |     &    |      and       |                  |----------|----------------|                  |     |    |      or        |                  |----------|----------------|                  |     ^    |      XOR       |                  |----------|----------------|                  |     ~    |      not       |                  |----------|----------------|                  |     >>   |   left shift   |                  |----------|----------------|                  |     <<   |   right shift  |                  +----------+----------------+`

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:                 |      1001018.to_s(2) => "10010"    |    & 1101026.to_s(2) => "11010"    |    --------                            |      1001010010 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 == 1end#bit manipulation, running time is O(1): def is_power_of_two(n)    return n > 0 && (n & (n - 1)) == 0end`

Similar to `logic or(||)` operator, `bitwise or` will return 1 if at least one of the bits is 1.

`18 | 26 => 26  Explain:                 |      1001018.to_s(2) => "10010"    |    | 1101026.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` .

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:                 |      1001018.to_s(2) => "10010"    |    ^ 1101026.to_s(2) => "11010"    |    --------                            |      010001000 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    resultend`

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                            |    --------                         |      00101Integer 27 in binary representation: 11011Applying two's complement, -27 is 00101, which is the same as ~26`

Manipulation:

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                                |   ------------                                       00000100The last 1 occurs at index 5.`

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                         |      --------                         |         100100 is the binary representation of 4 18 << 2 => 72            |Explain:                 |18.to_s(2) => "10010"    |       10010                         |        << 2                         |      --------                         |     10010001001000 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    resultend`

Written by