Gegeben ist ein Byte mit einem gesetzten Bit: i.e. 1,2,4,8,16,32,64,128
Die Position des gesetzten Bits soll gefunden werden:
i.e. Byte = 1 enstpricht Position 1
i.e. Byte = 64 entspricht Position 7
… ended up with deBruijn (without knowing then …)
package main
/*
int pos(int a){
int p = (a & 3) | ((a >> 1) & 6) | ((a >> 2) & 5) | ((a >> 3) & 4) | ((a >> 4) & 15) | ((a >> 5) & 2) | ((a >> 6) & 1);
return p;
}
*/
import "C"
import "fmt"
func main() {
a := 1
for i := 0; i < 8; i++ {
e := (a & 1) | (a & 2) | (a >> 1 & 4) | (a >> 4 & 8) // 1, 2, 4, 8
e |= ((a >> 1) & 2) | (a>>2)&1 // 3
e |= ((a >> 2) & 4) | (a>>4)&1 // 5
e |= ((a >> 3) & 4) | (a>>4)&2 // 6
e |= ((a >> 4) & 4) | ((a >> 5) & 2) | (a>>6)&1 // 7
fmt.Println(e)
a <<= 1
}
b := 1
for i := 0; i < 8; i++ {
a := b
e := a & 3 // (a & 1) | (a & 2) // 1, 2
a >>= 1 // b>>1
e |= a & 6 // (a & 4) | (a & 2) // 4, 3
a >>= 1 // b>>2
e |= a & 5 // (a & 1) | (a & 4) // 3, 5
// a >>= 1 // b>>3
e |= (a >> 1 & 4) // 6
a >>= 2 // b>>4
//e |= (a & 1) // 5
//e |= (a & 2) // 6
//e |= (a & 4) // 7
//e |= (a & 8) // 8
e |= a & 15 // 5, 6, 7, 8
e |= (a>>1)&2 | (a>>2)&1 // 7
fmt.Println(e)
b <<= 1
}
c := 1
for i := 0; i < 8; i++ {
a := c
e := (a & 3) | ((a >> 1) & 6) | ((a >> 2) & 5) | ((a >> 3) & 4) | ((a >> 4) & 15) | ((a >> 5) & 2) | ((a >> 6) & 1)
fmt.Println(e, int(C.pos(C.int(a))))
c <<= 1
}
// faster ! really this is as fast as
// : about 1 multiply,
// 1 bitwise shift operation,
// 1 bitwise 'AND' operation
// .. followed by one array uplook
// (found out this is deBruijn style)
// 111 101 001 100 010 110 011 000 '1101000111' (839*(1<<i))>>6)&7
//
// start with a map and a multipier '1101000111'
var deBruijnMap = [8]byte{4, 5, 2, 6, 3, 1, 8, 7} // ->{5, 2, 4, 0, 1, 3, 7, 6}
const mult = 839
for i := 0; i < 8; i++ {
a := 1 << uint(i)
fmt.Println(deBruijnMap[((mult*a)>>6)&7])
}
}