I have been tinkering with non-database stuff recently and I don't really have any of it in a place to share something fun about. So in the interim, here is a small collection of some tricks I like a lot.

I like bitwise tricks a lot. Here's a couple that are not particularly useful, but are fun and cool. If you like these, you should read Hacker's Delight.

1. Average of two numbers

The problem with computing the average of two numbers in the obvious way: (a + b) / 2, is that a + b might overflow, even when their average is perfectly well-defined. In two's complement arithmetic, this can cause problems:

var a int16 = 31000
var b int16 = 30000
fmt.Println((a + b) / 2)

-2268

A better way is to use (a & b) + (a^b)>>1:

var a int16 = 31000
var b int16 = 30000
fmt.Println((a & b) + (a^b)>>1)

30500

The reason this works is we're splitting the bits of a and b into "bits set in both a and b" and "bits set in only one of a and b." When computing the average of the former, we can just keep those bits, since they're going to be added together then divided by two. When computing the average of the latter, we need to divide by two, hence the right shift. Adding together these two averages gives us the average of the original a and b.

2. Popcount

The popcount of an integer is the number of bits in its representation set to 1:

popcount(1101) = 3
popcount(1001) = 2

Recall that when we represent an integer in twos complement, we make the most significant bit negative, so with a 4-bit number, we have bits representing -8, 4, 2, 1.

The cyclic shift by n of an integer is obtained by rotating its digits, moving the leftmost to be the rightmost and shifting everything else over:

shift(1101, 0) = 1101
shift(1101, 1) = 1011
shift(1101, 2) = 0111
shift(1101, 3) = 1110

Here's a silly fact: the sum of all of the cyclic shifts of a two's complement integer is the negation of its popcount.

Here's a loose reason you might suspect this to be true: this operation is linear and invariant under cyclic shifts, so whatever it computes must also be linear and invariant under cyclic shifts. This means it's probably some kind of function of the number of bits set. This doesn't tell us that it's specifically the negation, but, if it suggests that if it's something interesting, it's probably related to the popcount in some way.

To see why this is true more concretely, we need two facts:

• the all-ones two's complement number (1111) is -1 for any bit width, and
• when we take all the cyclic shifts of a number, every bit counts as every position exactly once.

This means that we can rearrange the additions to look like adding up the all-ones number n times; once for every set bit: 1111 + 1111 + 1111. Each of these contributes -1, so the result is the negative of the popcount.

3. Biased Coin from Unbiased Coin

I learned this trick from David MacIver in Phil Eaton's Systems Internals Discord.

Say we want to simulate a p-biased coin, that is, one which flips heads with probability p and tails with probability 1-p. But all we have access to is a stream of uniformly random bits. The result is that our algorithm will pick a result in an average of two bits, which might be kind of surprising.

The algorithm is:

def biased_coin(p):
  flip = get_random_bit()
  if p < 0.5:
    return 0 if flip == 0 else biased_coin(2 * p)
  if p > 0.5:
    return 1 if flip == 1 else biased_coin(2 * p - 1)
  return flip

It's easy to run some simulations and see that this works. Here's why it works: generating an infinite sequence of random bits can be seen as generating a random binary fraction, which we then compare to p. It's a way to compute rand() < p.

But we actually only need a finite number of bits to determine whether that number is less than or greater than p.

b_1 b_2 ...

Where b_i contributes 2^-i to the final number if it's 1, and 0 otherwise.

Imagine the interval [0, 1]. Each time we learn a new digit to this number, we're slicing in half the point in space where it could live. If the first digit is 1, we know that it lives in [0.5, 1], for example. And in that case, if we know p is less than 0.5, we know the number we generated is greater than p.

The computation we do on the recursion is just re-scaling p and the new area to continue this trick of slicing the space in half until we can conclusively say which way this number goes.