text: 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
  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.
  Power of Two - LeetCode
  Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared…
  leetcode.com
  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:
  Single Number - LeetCode
  Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your…
  leetcode.com
  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 ~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:
  Convert a Number to Hexadecimal - LeetCode
  Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two's complement method is…
  leetcode.com
  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