DEV Community: Vladislav

Bit tricks every programmer should know

Vladislav — Thu, 02 Jun 2022 19:06:30 +0000

Intro

Hey everyone, I bet during a regular day at work you guys rarely shift bits left and right, applying ^ (XOR) or & (AND). So today I want to shed some light on a few basic bit tricks that you all might find helpful (or maybe not).

Left Shift

The basic one, but let's refresh our memories here and look at examples of how the left shift <<< operator works.

Example:
Let's say we want to shift number 3 (11 in binary) by one bit to the left and it gives us 6 (110).
3 << 1 = 110 = 6
3 << 2 = 1100 = 12
3 << 3 = 11000 = 24

Code:

fn left_shift(num: usize, offset: usize) -> usize {
    num << i
}

Check if the Nth bit is set

This one is a bit trickier, it tells us whether the Nth bit from the right side is set to 1. And we gonna use & (AND) operator to do so.

Example:
Let's say we want to check if 0 or 3rd bits are set to 1 in number 8 (1000 in binary).

8 = 1000
if offset == 0:
1000 & 0001 = 0 -> false (not set)
if offset == 3:
1000 & 1000 = 1 -> true (set)

Code:

fn is_set(num: usize, offset: usize) -> bool {
    (num & (1 << offset)) != 0
}

Set Nth bit to 1

Ok, here we're actually going to set a particular bit to 1 in case it's 0, or keep it as 1 if it's already set to 1.

Example:
Let's continue playing with the number 8 (1000 in binary).
(8) 1000 set 3rd and 0th bit (from right) to 1
1000 | 1000 = 1000 == 8 (nothing changed since it was already 1)
1000 | 0001 = 1001 = 9 (set first bit to 1)

Code:

fn set_bit(num: usize, offset: usize) -> usize {
    num | (1 << offset)
}

Flip Nth bit

Here we continue playing with one bit at a time. Similar to the previous one, we do not only set the bit to 1 but actually flip the actual value of a bit. For this, we gonna use ^ (XOR)!

Example:
Again 8 is 1000 in binary
1000(8) ^ 1000(8) = 0 (flipped left 1 to 0)
1000 ^ 1001 = 1001 (flipped right 1)

Code:

fn flip_bit(num: usize, offset: usize) -> usize {
    num ^ (1 << offset)
}

Number complement (NOT)

This is another standard operator many people don't even know what is it for. ! (NOT) (in java it would be ~) inverts all bits of a particular number.

Example:
Let's take 9 as our integer (1001 in binary)
We can represent 9 as u8, u32, etc, let's consider u32 to resolve confusion.
!1001 = 11111111111111111111111111110110
Because = 1001 in 32-bit representation is actually:
00000000000000000000000000001001, so inverting all bits gives us 11111111111111111111111111110110, which is 4294967286 in decimal.

Code:

fn not(num: u32) -> u32 {
    !num
}

Clear Nth bit

This one is pretty straightforward, though the concept is quite interesting. The goal is to set Nth bit to zero.

Example:
Again the integer is going to be 9 (1001).
Then let's say we want to clear the first bit from the right side.
As we already know ! operator (complement) inverts all the bits for us. So we can shift 1 by offset to find the bit we're looking for.

1 << offset = 1 in our case (0th bit)
!1 = 1111111*0* (depending on type, let's keep u8)
return 1001 & 11111110 = 1000 (8)

Code:

fn clear_bit(num: usize, offset: usize) -> usize {
    let mask = !(1 << offset);
    num & mask
}

Calculating Hamming weight

Hamming weight is essentially a number of ones in a binary representation of a number. There is an interesting observation has been made by Brian Kernighan,coauthor of first C language Book, which we're going to use here.
Every time we apply n & (n - 1) where n is 32-bit integer, the rightmost bit becomes 0.

Example:
Let's take binary 01010101.
1st iteration: 01010100
2nd iteration: 01010000
3rd iteration: 01000000
So by counting a number of iterations we can calculate the number of ones.

Code:

fn hamming_weight (mut n: usize) -> usize {
    let mut count = 0;
    while n != 0 {
        n &= n - 1;
        count += 1;
    }
    return count;
}

Check if exactly one bit is set

Here is another interesting observation. If our number is a power of 2, then we can say that only one bit is set. To check this, we just need to subtract one and apply & operator!

Example:
8 = 1000
8 - 1 = 7 = 0111
1000 & 0111 = 0000 -> TRUE!

Code:

fn check_exactly_one_bit_is_set(num: usize) -> bool {
    num != 0 && (num & (num - 1)) == 0
}

Conclusion

I hope you find those little tricks as fascinating as I think of them and maybe even apply them in your regular job (but don't forget about code readability!).

Back of the Envelope Calculation

Vladislav — Sun, 10 Apr 2022 19:37:26 +0000

Intro

I found this topic rather misleading and always overcomplicated. Though I cannot disagree the version below is a lot more simplified than real life calculations, it's still covers 99% of the things you can encounter in your interview process.

What to estimate?

QPS - queries per second

RPS - reads per second

WPS - writes per second

Peak QPS = QPS * 2 (usually)

RW - read write ratio

Message size - size of the message in bytes if not given

Read Throughput - RPS * message size = N bytes per second

Write Throughput - WPS* message size = N bytes per second

💡 Throughput is how much data actually passed through and bandwidth is how much data CAN be passed through (network configuration)
Ex: 1gbps network bandwidth can pass 125mb/s

Storage - usually storage for N years

Replica storage - storage * 2-3 times

Cache storage - usually 20% of storage or so

Cache replica storage - cache storage * 2-3 times

Basic Numbers

seconds in a day - 24 * 60 * 60 = 86400, roughly 10^5

1 ASCI letter - 1 char

timestamp - 8 bytes (2^64)

10³ - 1kb

10⁶ - 1mb

10⁹ - 1gb

10¹² - 1tb

10¹⁵ - 1pb

10¹⁸ - 1eb

Powers of two

Power           Exact Value         Approx Value        Bytes
---------------------------------------------------------------
7                             128
8                             256
10                           1024   1 thousand           1 KB
16                         65,536                       64 KB
20                      1,048,576   1 million            1 MB
30                  1,073,741,824   1 billion            1 GB
32                  4,294,967,296                        4 GB
40              1,099,511,627,776   1 trillion           1 TB

Latency numbers every programmer should know

Latency Comparison Numbers
--------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy            10,000   ns       10 us
Send 1 KB bytes over 1 Gbps network     10,000   ns       10 us
Read 4 KB randomly from SSD*           150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
HDD seek                            10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from 1 Gbps  10,000,000   ns   10,000 us   10 ms  40x memory, 10X SSD
Read 1 MB sequentially from HDD     30,000,000   ns   30,000 us   30 ms 120x memory, 30X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Notes
-----
1 ns = 10<sup>-9</sup> seconds
1 us = 10<sup>-6</sup> seconds = 1,000 ns
1 ms = 10<sup>-3</sup> seconds = 1,000 us = 1,000,000 ns

Handy metrics based on latency numbers

Read sequentially from HDD at 30 MB/s
Read sequentially from 1 Gbps Ethernet at 100 MB/s
Read sequentially from SSD at 1 GB/s
Read sequentially from main memory at 4 GB/s
6-7 world-wide round trips per second
2,000 round trips per second within a data center

How to estimate?

Clarify number of daily users and number of total users.
Ask about number of request from user on average. From here you can get QPS.
Think about peak QPS, Reads and Writes.
Assume (clarify) message size.
Calculate throughput.
If it's possible think about average data size. And calculate storage and cache here.

Estimation example

You have 10M daily active users and each of them makes 100 read requests per day on average and new data is created 5 times per day.

RPS = 10M * 100 / 86400 = 12000 r/s

WPS = 10M * 5 / 86400 = 580 w/s

Peak QPS = 24000 r/s

Let's assume(clarify with the interviewer) that the average read message size is 50 bytes and the written message is 1kb.

Avg Read throughput 50 * 12*10^3 = 60kb/s

Avg Write throughput 1kb * 580 = 580kb/s

Here we can think about the type of data/metadata etc. Let's assume that you have clarified with your interviewer and the size of the new data is 1kb.

5 years storage - 10M * 1kb * 5 time per day * 365 days per year * 5 years = 91tb * 3 = 300tb with replicas.

Lets assume that you have only 10% of hot data and you agreed to use 20% as cache.

Cache storage - 10% * 90tb * 20% * 3 replicas = 5.5 tb