HyperLogLog Register Index

Problem

Given a 32-bit hash value and a precision p, return [bucket, rank] as used by a HyperLogLog register.

The top p bits select the bucket and the remaining 32 - p bits determine rank, which is one plus the number of leading zeros; an all-zero remainder gives rank 32 - p + 1. Return [0, 0] for a precision outside 1 to 32.

Hint

Split the hash into the top p selector bits and the remainder used for the leading-zero rank.

Test cases

case 1

in: [0,4]

expected: [0,29]

case 2

in: [4294967295,32]

expected: [4294967295,1]

case 3

in: [1,32]

expected: [1,1]

case 4

in: [3355443200,4]

expected: [12,1]

case 5

in: [123456789,8]

expected: [7,2]

Starter codePython

def hll_register_index(hash_value, precision):
    # Your code here
    pass

5 test cases · run your code against them in the editor