HackMD
tags: leetcode algorithm learning
How to take log2() very fast
Use a hash, a very special hash
ref =
https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers
ref =
https://hackmd.io/rdTVGkmxSzyTGV9j05qZvw?both
ref
= https://zhouer.org/DeBruijn/
First, deal with 2^N, to know how it works
For a power of 2, 00…010…00.
According to reference, there are 2048 possible B(m=2, k=5).
B(m=2, k=5) is a de Bruijn sequence, i.e., a 5-bit de Bruijn sequence.
One of B(m=2, k=5) is
00000111110001001010110011011101
= 0x7c4acdd
= 130329821
(00…010…00 * 0x7c4acdd) >> 5 is one-to-one-and-onto to [0, 31]
Python3 use big-number, never overflow, so I have to take mode to mimic overfloew
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Jul 15 06:17:25 2019
@author: y56
ref = https://hackmd.io/rdTVGkmxSzyTGV9j05qZvw?both
My small De Bruijn Test of 130329821:
0x07C4ACDD
00000111110001001010110011011101B
bit 31 - bit 27 00000 0
bit 30 - bit 26 00001 1
bit 29 - bit 25 00011 3
bit 28 - bit 24 00111 7
bit 27 - bit 23 01111 15
bit 26 - bit 22 11111 31
bit 25 - bit 21 11110 30
bit 24 - bit 20 11100 28
bit 23 - bit 19 11000 24
bit 22 - bit 18 10001 17
bit 21 - bit 17 00010 2
bit 20 - bit 16 00100 4
bit 19 - bit 15 01001 9
bit 18 - bit 14 10010 18
bit 17 - bit 13 00101 5
bit 16 - bit 12 01010 10
bit 15 - bit 11 10101 21
bit 14 - bit 10 01011 11
bit 13 - bit 9 10110 22
bit 12 - bit 8 01100 12
bit 11 - bit 7 11001 25
bit 10 - bit 6 10011 19
bit 9 - bit 5 00110 6
bit 8 - bit 4 01101 13
bit 7 - bit 3 11011 27
bit 6 - bit 2 10111 23
bit 5 - bit 1 01110 14
bit 4 - bit 0 11101 29
bit 3 - bit 31 11010 26
bit 2 - bit 30 10100 20
bit 1 - bit 29 01000 8
bit 0 - bit 28 10000 16
0x07C4ACDD is 5bit de Bruin Sequence
"""
anti_hash_table = [0,1,3,7,15,31,30,28,24,17,2,4,9,18,5,10,
21,11,22,12,25,19,6,13,27,23,14,29,26,20,8,16]
# Formally, I shall build a hash table
# but I am lazy so I use an anti hash table.
# And use `list.index(element_value)`
for x in range(32):
hash_key = ((0x7c4acdd * (2 ** x)) >> 27) % 32
print(anti_hash_table.index(hash_key))
use another B(2,5)
0x077CB531
00000111011111001011010100110001
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Jul 15 07:11:08 2019
@author: y56
ref = https://hackmd.io/rdTVGkmxSzyTGV9j05qZvw?both
0x077CB531U
00000111011111001011010100110001
l-shamnt binary decimal
0 00000 0
1 00001 1
2 00011 3
3 00111 7
4 01110 14
5 11101 29
6 11011 27
7 10111 23
8 01111 15
9 11111 31
10 11110 30
11 11100 28
12 11001 25
13 10010 18
14 00101 5
15 01011 11
16 10110 22
17 01101 13
18 11010 26
19 10101 21
20 01010 10
21 10100 20
22 01001 9
23 10011 19
24 00110 6
25 01100 12
26 11000 24
27 10001 17
28 00010 2
29 00100 4
30 01000 8
31 10000 16
"""
anti_hash_table = [0,1,3,7,14,29,27,23,15,31,30,28,25,18,5,11,22,13,26,
21,10,20,9,19,6,12,24,17,2,4,8,16]
# Formally, I shall build a hash table
# but I am lazy so I use an anti hash table.
# And use `list.index(element_value)`
for x in range(32):
hash_key = ((0x077CB531 * (2 ** x)) >> 27) % 32
print(anti_hash_table.index(hash_key))
hash_table = []
for i in range(32):
hash_table.append(anti_hash_table.index(i))
for x in range(32):
hash_key = ((0x077CB531 * (2 ** x)) >> 27) % 32
print(hash_table[hash_key])
Second, convert numbers to 2^N
Set all bits right to MSB to 1
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value |= value >> 32;
value = value - value >> 1;
Set all bits right to MSB to 0
value -= value >> 1;
Hash it. As before.
(0x7c4acdd * value) >> 27;
Using Python3
anti_hash_table = [0,1,3,7,15,31,30,28,24,17,2,4,9,18,5,10,
21,11,22,12,25,19,6,13,27,23,14,29,26,20,8,16]
def log2_32(value):
value |= value >> 1
value |= value >> 2
value |= value >> 4
value |= value >> 8
value |= value >> 16
return anti_hash_table.index(
((
(value - (value >> 1 ))
* 0x7c4acdd)
>> 27
) % 32)
Third, use a new hashing to replace the conversion from 2^(N+1)-1 to 2^N
Originally,
log2_32 (uint32_t value) {
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[((uint32_t)((value - (value >> 1 ))*0x7c4acdd)) >> 27];
Focus on
(value - (value >> 1 ))*0x7c4acdd # confirmed
It is equal to
value*0x7c4acdd - (value>>1)*0x7c4acdd # confirmed
= value0x7c4acdd - ((value-1)/2) * 0x7c4acdd
= value0x7c4acdd - (value*0x7c4acdd/2 - 0x7c4acdd/2)
Then equal to
value*0x7c4acdd - (value*(0x7c4acdd>>1)) # WRONG!!!
Then
value*0x7c4acdd - value*(0x7c4acdd>>1) # WRONG!!!
Then
value*(0x7c4acdd-(0x7c4acdd>>1) # WRONG!!!
Then
value*(0x3e2566f) # WRONG!!!
```~~
```python=
anti_hash_table = [0,1,3,7,15,31,30,28,24,17,2,4,9,18,5,10,21,11,22,12,25,19,6,13,27,23,14,29,26,20,8,16]
def log2_32(value):
value |= value >> 1
value |= value >> 2
value |= value >> 4
value |= value >> 8
value |= value >> 16
return anti_hash_table.index((((
(value*0x7c4acdd - (value>>1)*0x7c4acdd)
) >> 27 ) % 32))
Finally
I don't know how to convert DB for 0..01..1 to DB for 0..010..0
hash_table = [ 0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31]
def log2_32(value):
value |= value >> 1
value |= value >> 2
value |= value >> 4
value |= value >> 8
value |= value >> 16
return hash_table[((
(value*0x7c4acdd
) >> 27 ) % 32)]
We can use gcc built-in function
https://www.cnblogs.com/nysanier/archive/2011/04/19/2020778.html
https://github.com/y56/proving-ground/tree/master/gcc-builtin-bitwise
