Card 08/ 08
Recap: Bit Manipulation
Six operators on a row of bits, five one-line tricks, and three places where the languages disagree.
Bit manipulation treats an integer as a row of bits and changes them with six operators, each one step: AND keeps shared bits, OR keeps either, XOR keeps exactly one, NOT flips them all, and the shifts move every bit one place. XOR cancels pairs, so it finds an unpaired or missing value in O(1) extra space. Five tricks do the common jobs, each shown here on 44, which is 101100:
| Task | Expression | On 44 | Note |
|---|---|---|---|
| Test bit k | (x >> k) & 1 | Bit 2: 1 | 1 when bit k is on, 0 when it is off |
| Set bit k | x | (1 << k) | Bit 0: 45 | Leaves every other bit alone |
| Clear bit k | x & ~(1 << k) | Bit 3: 36 | ~ turns the mask round so only bit k is 0 |
| Clear the lowest set bit | x & (x - 1) | 40 | Repeat until 0 to count the set bits |
| Isolate the lowest set bit | x & -x | 4 | Works because −x is ~x + 1 |
| Power of two | x > 0 and x & (x - 1) is 0 | No | 0 also gives 0, so exclude it |
| Count the set bits | The loop, int.bit_count() or Integer.bitCount | 3 | TypeScript has no built-in count |
The languages disagree in three places. Python's integers have no fixed width, so 1 << 31 is 2147483648; in a Java int and in TypeScript's bitwise operators it is −2147483648. TypeScript's |, & and shifts drop every bit above the 32nd, so (2 ** 32 + 5) | 0 is 5. And >> copies the sign bit in Java and TypeScript, so a sign test needs & 1 after the shift or the unsigned >>>.
← → move through sections and cards