Understanding the bitwise left shift logic on determining nSubsidy

Question

I'm trying to understand how the >>= operation in nSubsidy >>= (nBestHeight / 210000); actually cuts the subsidy in half every 4 years on Bitcoin v0.01.

It is clear how 210000 blocks average out to around 4 years and how dividing the last block height will return an integer that will give us the number of time it needs to be halved. What is confusing is how just shifting a bit on nSubsidy will give us the desired subsidy.

I wrote this loop to help visualize the shift in bits but still unclear how in binary, a simple 1 bit shift gets us the desired result.

#include <iostream>
#include <bitset>

int main()
{
    uint64_t COIN = 100000000;
    uint64_t nSubsidy; 
    std::string binary;

    //halving and non halving block height examples
    uint64_t nBestHeight[] = {-1, 0, 1, 210000, 210001, 420000, 420001, 630000, 630001, 840000, 840001, 1050000, 1050001};

    for(unsigned int a = 0; a < sizeof(nBestHeight)/sizeof(nBestHeight[0]); a = a + 1 )
    { 
        nSubsidy = 50 * COIN;

        //Shift bits
        nSubsidy >>= (nBestHeight[a] / 210000);

        //Convert to binary to visualize bit shift
        binary = std::bitset<64>(nSubsidy).to_string();

        std::cout << "nSubsidy (64 bit binary) = " << binary << "    |    (nBestHeight/210000) = " << (nBestHeight[a] / 210000) << "    |    nSubsidy = " << nSubsidy << "    |    nBestHeight = " << nBestHeight[a] << "\n";
    }

}

/*

OUTPUT

BINARY TO VISUALIZE BIT SHIFT                                                                       HALVING ERA                      MINING REWARD                 CURRENT BLOCK HEIGHT
nSubsidy (64 bit binary) = 0000000000000000000000000000000100101010000001011111001000000000    |    (nBestHeight/210000) = 0    |    nSubsidy = 5000000000    |    nBestHeight = 0
nSubsidy (64 bit binary) = 0000000000000000000000000000000100101010000001011111001000000000    |    (nBestHeight/210000) = 0    |    nSubsidy = 5000000000    |    nBestHeight = 1
nSubsidy (64 bit binary) = 0000000000000000000000000000000010010101000000101111100100000000    |    (nBestHeight/210000) = 1    |    nSubsidy = 2500000000    |    nBestHeight = 210000
nSubsidy (64 bit binary) = 0000000000000000000000000000000010010101000000101111100100000000    |    (nBestHeight/210000) = 1    |    nSubsidy = 2500000000    |    nBestHeight = 210001
nSubsidy (64 bit binary) = 0000000000000000000000000000000001001010100000010111110010000000    |    (nBestHeight/210000) = 2    |    nSubsidy = 1250000000    |    nBestHeight = 420000
nSubsidy (64 bit binary) = 0000000000000000000000000000000001001010100000010111110010000000    |    (nBestHeight/210000) = 2    |    nSubsidy = 1250000000    |    nBestHeight = 420001
nSubsidy (64 bit binary) = 0000000000000000000000000000000000100101010000001011111001000000    |    (nBestHeight/210000) = 3    |    nSubsidy = 625000000     |    nBestHeight = 630000
nSubsidy (64 bit binary) = 0000000000000000000000000000000000100101010000001011111001000000    |    (nBestHeight/210000) = 3    |    nSubsidy = 625000000     |    nBestHeight = 630001
nSubsidy (64 bit binary) = 0000000000000000000000000000000000010010101000000101111100100000    |    (nBestHeight/210000) = 4    |    nSubsidy = 312500000     |    nBestHeight = 840000
nSubsidy (64 bit binary) = 0000000000000000000000000000000000010010101000000101111100100000    |    (nBestHeight/210000) = 4    |    nSubsidy = 312500000     |    nBestHeight = 840001
nSubsidy (64 bit binary) = 0000000000000000000000000000000000001001010100000010111110010000    |    (nBestHeight/210000) = 5    |    nSubsidy = 156250000     |    nBestHeight = 1050000
nSubsidy (64 bit binary) = 0000000000000000000000000000000000001001010100000010111110010000    |    (nBestHeight/210000) = 5    |    nSubsidy = 156250000     |    nBestHeight = 1050001

*/

Is it really that just by shifting a bit to right or to the left we duplicate or half the value? Are there any resources or any other terminology to verify this better? Are the above assumptions even right?

Answer 1

This isn't really a Bitcoin question, just a math one, but I'll give it a shot anyways.

Let's look at the binary values for a few numbers from base 10

0    | 0
1    | 1
2    | 10
3    | 11
4    | 100
5    | 101
6    | 110
7    | 111
8    | 1000
9    | 1001
10   | 1010

Note how the powers of two set the (nth+1) bit (when read right to left) - 2^0 sets the 1st bit, 2^1 sets the second, 2^2 sets the third and so on.

Since a power of two is simply the previous power of two multiplied by two, shifting one bit to the right achieves a division by 2.

For example, if we shift 8 (1000 in binary) by 1 bit:

1000 >> 1 -> 100

Similarly shifting 1010 (10 in base 10) by one bit, we get:

1010 >> 1 -> 101

This produces 101, which is 5 in base 10.

Naturally, this produces some loss of precision in the form of flooring. For example, if we try this with 9 (1001 in binary):

1001 >> 1 -> 100

We get 100, which is 4 - the 0.5 from 9/2 is lost.

However, since bitcoin's internal definitions are in Satoshis, not BTC, we will not lose any precision until reward era 11, starting with block 2,100,000, at which point we will lost 0.5 satoshi to precision loss.