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
Operation | Result |
---|---|
1111 ^ 0000 | 1111 |
1111 ^ 0001 | 1110 |
1111 ^ 0010 | 1101 |
1111 ^ 0100 | 1011 |
JavaScript Bitwise Operators
注意:从英语学习的角度另给了口语化的英文解释。
Operator | Name | Description |
---|---|---|
& | AND | Sets each bit to 1 if both bits are 1
compares two equal-length bit patterns; returns one in positions where both patterns have ones, otherwise returns zero |
| | OR | Sets each bit to 1 if one of two bits is 1
compares two equal-length bit patterns; returns one if either pattern has a one in that position, otherwise zero |
^ | XOR | Sets each bit to 1 if only one of two bits is 1
also compares two equal-length patterns; only returns one in positions where the patterns are different |
~ | NOT | Inverts all the bits.
flips every bit to its opposite |
<< | Zero fill left shift | Shifts left by pushing zeros in from the right and let the leftmost bits fall off shifts the pattern a certain number of bits (given after the operator) and adds zeroes to the end; equivalent to multiplying the starting number by 2**n, where n is the number to shift |
>> | Signed right shift | Shifts right by pushing copies of the leftmost bit in from the left, and let the rightmost bits fall off
shifts the pattern a certain number of bits to the right and appends one at the end; equivalent to dividing by 2**n, where n is the number to shift |
>>> | Zero fill right shift | Shifts right by pushing zeros in from the left, and let the rightmost bits fall off |
Examples
Operation | Result | Same as | Result |
---|---|---|---|
5 & 1 | 1 | 0101 & 0001 | 0001 |
5 | 1 | 5 | 0101 | 0001 | 0101 |
~ 5 | 10 | ~0101 | 1010 |
5 << 1 | 10 | 0101 << 1 | 1010 |
5 ^ 1 | 4 | 0101 ^ 0001 | 0100 |
5 >> 1 | 2 | 0101 >> 1 | 0010 |
5 >>> 1 | 2 | 0101 >>> 1 | 0010 |
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
版权声明:本文标题:Bit manupulation in JS英文 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1727935016a1138828.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论