Category Archives: Bit Manipulation

Bit Manipulation, Interview Questions

Single Number (Leetcode)

I don’t like this one. Let’s discuss two solutions:

Natural Solution

Here’s a natural-enough solution in Python. Observe how we use a “counter” object; that’s basically a hashmap, which is a fine-enough solution as well in my opinion. This is, in my opinion, the “right” solution.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counter = collections.Counter()
        for n in nums:
            counter[n] += 1
        for n in counter:
            if counter[n] == 1: return n
        # return None, assert.

This is “inefficient”, in the sense that we’re using O(n) space and a bit more than O(n) time (I’m a pedant about hashmap time). However, it solves the general problem of “what’s the unique element in this sequence”. That problem isn’t super-common, but it’s not way-out-there.

Desired Solution

But! They want constant space and linear time. This is a nice enough “think outside the box” thing, but it’s so obviously fishing for a trick after-the-fact. It’s a tail-wagging-the-dog sort of situation, where someone obviously observed an interesting trick, and then constructed a question that can only be reasonably answered with that trick. What’s the trick? It involves XOR identities.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda a, b: a ^ b, nums)

Ooooh. The observation is that for XOR operation (the ^ operator):

  • a^a = 0
  • a^0 = a
  • And everything commutes

So a sequence like a^a^b^b^c = c, because we end up with 0^0^c=c. That’s neat, but extremely dependent on the idea that the sequence contains an even number of every element, except one, which exists an odd number of times. I suppose it’s neat to keep the “flexibility” of thinking of array contents as values (as we do in the typical solution) and bit-sequences, but it’s really a fishing sort of question.

I’d do this for fun (I did do this for fun), but I’d suggest avoiding it except to show a neat consequence of XOR identities in a classroom. More bit manipulation questions here.

Bit Manipulation, Dynamic Programming, Interview Questions

Counting Bits (Leetcode)

Another from the archives! I had a lot of fun with this one. Would others? I don’t know! We can use a sort-of dynamic programming approach (maybe this is a good replacement for that frustrating “Fib” standard warmup?) to avoid calling popcount over and over again. Not sure what’s actually faster on hardware, but I like the principle here.

This is a good algorithmic-thinking question, I think. Requires some fluency with bit manipulation, though.

class Solution {
public:
    vector<int> countBits(int num) {
        if (num == 0) { return {0}; }
        if (num == 1) { return {0, 1}; }
        if (num == 2) { return {0, 1, 1}; }
        vector<int> res(num+1);
        res[0] = 0;
        res[1] = 1;
        for (int i = 2; i <= num; ++i) {
            const int lastBit = i % 2;
            res[i] = res[i/2] + lastBit;
        }
        return res;
    }
};

Notes

Additional implementation details? I don’t know. I found it reassuring that the length of the output is required to be num, because there’s always that potential psuedopolynomial trap. Fixing the output size (versus, say, we’d have to return the total numbers of 1s or something) helps make it unambiguous that we’d at least be able to iterate through all inputs.

Other bit-manipulating questions are collected here. Other dynamic-programming questions are collected here.

Bit Manipulation, Interview Questions

Displaying Sum in Binary (Code Wars 3)

1 Comment

Here is the next codewars problem. It’s a bit strange: you get two “normal” numbers, and then you need to return their sum as a binary string. Adding two numbers is pretty straightforward in this case: you use the +, to be humorous about this.

Already you can see we have another case of bitwise manipulation! We can use the same trick, again, to iterate through all the bits in our sum and add them to a string.

I had a bug! First, here is the (validated) solution:

def add_binary(a,b):
    assert(a >= 0 and b >= 0)
    s = a + b
    result = []
    while s > 0:
        oldS = s
        result.append(str(s % 2))
        s = s // 2
    result = ''.join(reversed(result))
    return result

Let’s focus on the positives.

  1. The assert on line 2 is my own sanity-checking. Things can get funny in this question if a or b can be negative.
  2. You can barely see where the sum happens in this question: line 3. After that, you can see we completely ignore a, b.
  3. This has a fun combination of the previous 2 questions we talked about. We build up our string as a list of strings (each element in that list is either the string “0” or “1”) and join that list over the empty string. Just as we saw ‘ ‘.join(…) in the previous question, how it combined all the elements into a string, separating each element by ‘ ‘, this combines all elements in our list as a string, separated by ”, i.e., separated by nothing.
  4. We determine the “next” bit of s with s % 2, just like before. A big change (and this is where the bug is) is on line 8. Previously, we did s = int(s/2), and my initial implementation had that as well. In tests with extremely large integers, that method failed. Let’s discussion why.

The Bug

This is a somewhat advanced bug. Truth be told, if a beginner programmer (esp. from a bootcamp) hit this issue, I’m not sure if they’d have the context to address it. Here’s what happens:

  1. Python distinguishes between integers, which are whole numbers, and floats, which are numbers that can have a decimal point. Adding two integers always gives you the answer you’d expect, so integers are simple. Floating point numbers ultimately have to round (similar to how, with 0.333333333…, eventually you have to decide when to stop writing 3s!).
  2. In our code, s is an integer, except when it’s being divided by 2. Python will automatically convert it into a float. That is why we immediately turn it back into an integer, with int(s/2). This gives the effect of “chopping off” anything after the decimal point, which is what we want. (We’d expect the decimal to either be .0, when s was previously even, or 0.5, when s was previously odd.)
  3. However, that rounding that we have to do with floating-point-numbers doesn’t just happen after the decimal point. For very large numbers, the rounding can happen in the thousandth’s place, or similar (so rather than a big number ending with 124,325.0, it would look like 124,000.0). This truncation is too aggressive!
  4. So the bug manifested that we were outputting a binary number with just a long string of 0s at the end, when it should have been a mix of 0s and 1s.
  5. The fix was me searching around online until I found out how to do truncating-integer-division in Python. That avoids converting the integer into a double, and therefore we never introduce that inadvertent rounding, and we get the right answer!
Bit Manipulation, Interview Questions

Bit Counting (Code Wars 1)

1 Comment

Sometimes it can be useful to think about numbers as an array of bits. This question asks us to consider a number in that way, and then count the number of elements in that array that are “1”. The link.

The first key realization is really considering how a number is an array-of-bits. That has a lot of follow-on implications. In particular, it suggests that maybe we can write code like the following:

def count_bits(n):
    counter = 0
    for bit in n:
        if bit == 1:
            counter += 1
    return counter

This code is a solution! We would count all the bits that are 1. The issue is that key line, “for bit in n“, doesn’t really exist. How might we address this? Fortunately, I’ve seen this problem many times, or similar-enough ones, and I’ll present a solution and discuss it.

def count_bits(n):
    counter = 0
    while n > 1:
        if n % 2 == 1:
            counter += 1
        n = int(n/2)
    return counter

That was quick!

Approach

  1. The if on line 4 of our solution is essentially testing the least-significant bit in n. So in that way we can look at a single bit in n, and emulate the condition in our “ideal” loop.
  2. The n = int(n/2) on line 6 essentially chops off the last binary digit of n. Just as dividing a normal number by 10 (and rounding down) has the effect of trimming off the last decimal digit of a number, so too does dividing by 2 and rounding down trim off the last binary digit (i.e., the last bit) of the number.
  3. That “trimming” gives us the effect of iterating through every bit of n, accessing that bit with the modulo (%) operator. In this way we can see if the rightmost bit is 1 or 0 (again, using the if statement mentioned in point 1.)

Bit-related questions don’t come up too often, but the “trick” we have here to iterate through a number as a sequence of bits is a useful staple in these bitwise questions. All bit manipulation questions so far on the sight should be collected here.