Bit manupulation in JS英文

admin管理员组

文章数量:1584215

Common Bit Manipulation Problems

The most common bit manipulation problem is likely checking if a number is a power of two (there is a readily available one on Leetcode). The solution looks simple, but is actually rather difficult to understand at first.

const isPowerOfTwo = n => {
  return (n && !(n & (n - 1)))
}

What does this mean? We know we’re returning a boolean. The first half of the return checks if n is truthy; that is, non-zero. This takes care of checking if zero is a power of two. The second part takes advantage of our bitwise AND operator to compare two equal-length bit patterns: n and n-1. Let’s look at that second part a little more clearly with some examples.

8 is a known power of 2
8 passes the first test; it is truthy since it is not zero
What about 8 & 7? Let's look at them both as binary code
8 = 1000 (2**3 + 0 + 0 + 0)
7 = 0111 (0 + 2**2 + 2**1 + 2**0)
So the operation 8 & 7 results in 0000 (falsey)
Therefore, doing !(8 & 7) gives us a truthy value
Our function returns true! 8 is a power of 2!

This is how the test works: all powers of two will only have a single one in their binary representation — the place at which they are a power of two. Subtracting one from a power of two, however, results in a number with many other instances of the number one, thereby causing the result of the bitwise AND operator on both patterns to always return false. Since we check for whether this is false, we get a boolean return of true when our input is a power of two.

Another common bit manipulation problem is counting the number of ones in a binary representation of a number. This is also known as the Hamming weight, which I find endlessly delightful because it conjures up images of county fairs where, instead of the hammer and bell, the strong man lifts an enormous blue-ribbon pig. I digress. Again, reliable Leetcode has an example ready.

const hammingWeight = n => { 
  let count = 0;
  while(n){
    n = n & (n - 1)
    count++
  }
  return count
}

Again, a seemingly simple solution that is actually rather hard to understand. Let’s again break it down with some examples.

Find the Hamming weight of 103
First, we see our count is 0
Then, while n -> meaning whenever n is not zero
Next, we are setting n to now equal n & (n - 1) and then incrementing our count variable
For 103, the binary representation is 2**6 + 2**5 + 2**2 + 2**1 + 2**0, or 1100111
For 102, our initial n - 1, the binary would be 1100110
So on first loop, n & (n - 1) would be 1100110, and our counter iterates for the 1 that was in the 2**0 placeOn the next loop:
n = 1100110 (102)
n - 1 = 1100101 (101)
n = n & (n - 1) = 1100100 (100) -> counter is now up to 2Next loop:
n = 1100100 (100)
n - 1 = 1100011 (99)
n = n & (n - 1) = 1100000 (96) -> counter is now up to 3Next loop:
n = 1100000 (96)
n - 1 = 1011111 (95)
n = n & (n - 1) = 1000000 (64) -> counter is now up to 4Last loop: 
n = 1000000 (64)
n - 1 = 0111111 (63)
n = n & (n - 1) = 0 -> counter is now up to 5While loop stops because while(n) is no longer valid
Counter is returned (5) -> check for accuracy
103 was 1100111 -> 5 ones!

The key insight of this method is that setting a number to the result of the bitwise AND operator on the number’s previous value and its decrement ‘flips’ all the bits to the right of each place in the number incrementally until that number is zero, thereby ‘removing’ all of the ones. As long as this process is tracked by a variable, the number of one bits can be counted and returned.

Plus：The solutions of Hamming distance 

Learning stuffs

^ Examples

JavaScript Bitwise Operators

注意：从英语学习的角度另给了口语化的英文解释。

Examples

Hopefully this brief introduction to bit manipulation in JavaScript has provided new information and perspective on ways to write certain algorithms. I know I am still struggling to grasp some of the more advanced bitwise concepts, so I may have to return with a second installment once I better untangle those issues.

本文标签： 英文bitmanupulationjs