# 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.

## Operators meaning and symbol

` +----------+----------------+`

| Symbol | Meaning |

|----------|----------------|

| & | and |

|----------|----------------|

| | | or |

|----------|----------------|

| ^ | XOR |

|----------|----------------|

| ~ | not |

|----------|----------------|

| >> | left shift |

|----------|----------------|

| << | right shift |

+----------+----------------+

**And operator:**

The

operator is applying **bitwise and**

to binary representations of two numbers. The rule is return 1 if both bits are 1, otherwise, return 0.**logic and(&&)**

`18 & 26 => 18 |`

**Explain: **| 10010

18.to_s(2) => "10010" | & 11010

26.to_s(2) => "11010" | --------

| **1**00**1**0

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

operator, **logic or(||)**

will return 1 if at least one of the bits is 1.**bitwise or**

`18 | 26 => 26 `

Explain: | 10010

18.to_s(2) => "10010" | | 11010

26.to_s(2) => "11010" | --------

| **11**0**1**0

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

and **bitwise and**

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 **bitwise or***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 ~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

| ------------

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