Monthly Archives: Dezember 2017

Find position of bit in byte with one bit set

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])
  }

}