blob: 513786c2bfffa73635f68faad4e26a00d5c490da (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
package main
// floor of log(x) (i.e MSB for positive integers)
func Log(x int64) int64 {
var r int64 = 0
for ; x > 1; x >>= 1 {
r++
}
return r
}
// squared exponentiation
func Pow(x int64, n int64) int64 {
var r int64 = 1
for i := n; i > 0; i >>= 1 {
if i&1 == 1 {
r *= x
}
x *= x
}
return r
}
// convert BFS order to DF-post-order, dark magic
func Post(size int64, height int64, id int64) int64 {
id += 1
s := int64(1) << uint64(height-Log(id)) // size of the substree rooted at id
r := s - 2
for ; id > 1; id >>= 1 {
if id&1 == 1 { // right child
r += s - 1
}
s <<= 1
}
return r
}
|
