Bit manipulation

When to use it

Use it when the task is about the 0s and 1s a number is stored as, not its decimal digits, or when each bit can stand for one yes or no.

It belongs to the math & bits group: Work on the cells, the digits or the bits themselves, in a fixed order.

Watch it work

Three friends each keep their free days of one week in a number. The rightmost bit is Monday, the next is Tuesday, and so on; a 1 means free. Return the first day all three are free, with Monday as 0, or -1 if there is none.

Input
weeks = [45, 110, 57]

Output
3

The method

1. Start with the free days of the first friend
2. AND (&) with each friend: a 1 stays only where both have 1
3. If no 1 bit is left, no day suits everyone
4. While the last bit is 0, drop it with a right shift (>>)
5. The last bit is 1: this day is the first that suits all

The run, one moment at a time

1. Step 1. Mia's number is 45, which is 32 + 8 + 4 + 1, so her row has a 1 under each of those. Read the bits from the right: free on Monday, Wednesday, Thursday and Saturday. Start with these days.

   worth: 64 32 16 8 4 2 1
   Mia 45: 0 1 0 1 1 0 1
   Leo 110: 1 1 0 1 1 1 0
   Zoe 57: 0 1 1 1 0 0 1
   common: 0 1 0 1 1 0 1  (Sun at 0, Sat at 1, Fri at 2, Thu at 3, Wed at 4, Tue at 5, Mon at 6)
   

2. Step 2. AND, written &, keeps a 1 only where both numbers have a 1. Leo is not free on Monday, so that bit becomes 0. Wednesday, Thursday and Saturday stay, so common is 44.

   worth: 64 32 16 8 4 2 1
   Mia 45: 0 1 0 1 1 0 1
   Leo 110: 1 1 0 1 1 1 0
   Zoe 57: 0 1 1 1 0 0 1
   common: 0 1 0 1 1 0 0  (Sun at 0, Sat at 1, Fri at 2, Thu at 3, Wed at 4, Tue at 5, Mon at 6)
   

3. Step 2. AND with Zoe's number. Zoe is not free on Wednesday, so that bit becomes 0. Thursday and Saturday stay, so common is 40.

   worth: 64 32 16 8 4 2 1
   Mia 45: 0 1 0 1 1 0 1
   Leo 110: 1 1 0 1 1 1 0
   Zoe 57: 0 1 1 1 0 0 1
   common: 0 1 0 1 0 0 0  (Sun at 0, Sat at 1, Fri at 2, Thu at 3, Wed at 4, Tue at 5, Mon at 6)
   

4. Step 3. common is 40, not 0, so at least one bit is 1 and a day that suits everyone exists. A 0 here would mean no such day, and the answer -1.

   common: 0 1 0 1 0 0 0  (Sun at 0, Sat at 1, Fri at 2, Thu at 3, Wed at 4, Tue at 5, Mon at 6)
   day: 0
   

5. Step 4. common & 1 keeps only the last bit, because 1 is 0000001. It was 0, so Monday is out. >> drops that bit and moves the others one place right; the empty place in front shows 0. day is 1.

   common: 0 0 1 0 1 0 0  (Sun at 1, Sat at 2, Fri at 3, Thu at 4, Wed at 5, Tue at 6)
   day: 1
   

6. Step 4. The last bit was 0 again, so Tuesday is out. Shift right once more: the bit of Wednesday is now last, and day is 2.

   common: 0 0 0 1 0 1 0  (Sun at 2, Sat at 3, Fri at 4, Thu at 5, Wed at 6)
   day: 2
   

7. Step 4. The last bit was 0 again, so Wednesday is out. Shift right once more: the bit of Thursday is now last, and day is 3.

   common: 0 0 0 0 1 0 1  (Sun at 3, Sat at 4, Fri at 5, Thu at 6)
   day: 3
   

8. Step 5. The last bit is 1, so Thursday suits everyone. 3 bits were dropped before it, so the answer is 3, with Monday counted as 0.

   common: 0 0 0 0 1 0 1  (Sun at 3, Sat at 4, Fri at 5, Thu at 6)
   day: 3
   

The code

The numbered comments are the steps of the method.

function solve(weeks) {
  // 1. Start with the free days of the first friend
  let common = weeks[0];
  for (let i = 1; i < weeks.length; i++) {
    // 2. AND (&) with each friend: a 1 stays only where both have 1
    common = common & weeks[i];
  }
  // 3. If no 1 bit is left, no day suits everyone
  if (common === 0) return -1;
  // 4. While the last bit is 0, drop it with a right shift (>>)
  // 1 has only its last bit on, so & 1 keeps only the last bit.
  let day = 0;
  while ((common & 1) === 0) {
    common = common >> 1;
    day += 1;
  }
  // 5. The last bit is 1: this day is the first that suits all
  return day;
}

def solve(weeks):
    # 1. Start with the free days of the first friend
    common = weeks[0]
    for i in range(1, len(weeks)):
        # 2. AND (&) with each friend: a 1 stays only where both have 1
        common = common & weeks[i]
    # 3. If no 1 bit is left, no day suits everyone
    if common == 0:
        return -1
    # 4. While the last bit is 0, drop it with a right shift (>>)
    # 1 has only its last bit on, so & 1 keeps only the last bit.
    day = 0
    while (common & 1) == 0:
        common = common >> 1
        day += 1
    # 5. The last bit is 1: this day is the first that suits all
    return day

How to spot it

Asked: The task asks about the 0s and 1s a number is stored as

Bit operators reach single bits directly. AND with 1 reads the last bit, and a shift right moves the next bit into its place.

Given: Every item has some of at most 30 yes or no properties

One bit holds one yes or no, so a whole set fits in one number. AND and OR then combine two sets in one step.

Limits: The + and - operators are not allowed

When ordinary arithmetic is ruled out, only the bits are left to work with. The bit operators can rebuild it from them.

Limits: Every value comes twice except one, and extra memory must stay constant

XOR, written ^, gives 0 for two equal numbers. So pairs cancel each other, and one number does the work of a set.

Looks like it, but is not

• The number arrives as a string or a list of decimal digits. Use Digit-by-digit arithmetic. Those are decimal digits kept apart, not the bits of a stored number. You work through them with a carry, as on paper.
• You must list every value that appears more than once, and memory is not limited. Use Hash set membership. XOR makes pairs disappear, so it cannot name them. A set that remembers each value seen answers this directly.
• You need the same fact about the bits of every number from 0 up to n. Use One-dimensional dynamic programming. The answer for a number can be built from the answer for a smaller number. That reuse is the main idea, not the bit test.

Cost and mistakes

Time is one AND for each number in the list, about n steps, written O(n), and then fewer than 7 shifts, one for each day passed over. Extra space is one number, written O(1), because a whole week fits in its bits.

Watch out

• ^ is not a power, in JavaScript or in Python. It is XOR: it gives a 1 where the two bits differ. So 2 ^ 3 is 1, not 8. A power is written **.
• In JavaScript x & 1 === 0 does the comparison first and the & after, so it is wrong. Write (x & 1) === 0. Python does the & first, but keep the brackets there too.
• JavaScript's bit operators work on 32 bits, and the top bit is the sign, so 1 << 31 is negative. Python numbers have no fixed size, so there it is 2147483648.

In the 150

5 problems of the 150 use it. Naming them gives their method away, so the list is folded.