Bit manipulation golang

Question

I'm looking at a codebase with the following:

const IdLength = 20

type NodeID [IdLength]byte

func (node NodeID) PrefixLen() (ret int) {
  for i := 0; i < IdLength; i++ {
    for j := 0; j < 8; j++ {
      if (node[i] >> uint8(7 - j)) & 0x1 != 0 {
        return i * 8 + j;
      }
    }
  }
  return IdLength * 8 - 1;
}

I can't quite grasp what's happening here. Could someone explain it to me with an example?

Answer 1

This takes as input a variable number of bytes which are really treated as bits. It returns the number of leading 0 bits in the stream of bytes. Say you have these bytes:

0x00 0x00 0x05

which in binary looks like this

00000000 00000000 00000101

which means the function returns 8+8+5 = 21.

The outer loop with i as the variable goes over all bytes, the inner loop with j as the variable goes over all bits in that byte. It shifts the jth bit from the top, down to the lowest bit, the binary and (&) with 0x01 masks all but that lowest bit, then != 0 asks if this bit is 1 in which case we are at the end of the 0 prefix and return the result.

If at the end of the function there was no early return, all bytes are 0 so it returns the value for that. That special case does not return 208 but 208-1 for some reason. This is specific to the application I guess. I would have expected it to return all zeros, but it returns one fewer.

Here is a code example with the outputs as comments:

package main

import "fmt"

func main() {
    fmt.Println(NodeID{0xFF}.PrefixLen()) // 0
    fmt.Println(NodeID{0x7F}.PrefixLen()) // 1
    fmt.Println(NodeID{0x3F}.PrefixLen()) // 2
    fmt.Println(NodeID{0x1F}.PrefixLen()) // 3
    fmt.Println(NodeID{0x0F}.PrefixLen()) // 4
    // ...
    fmt.Println(NodeID{0x00, 0x00, 0x05}.PrefixLen()) // 21
    // ...
    fmt.Println(NodeID{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}.PrefixLen()) // 159
    fmt.Println(NodeID{}.PrefixLen()) // 159
}

const IdLength = 20

type NodeID [IdLength]byte

func (node NodeID) PrefixLen() (ret int) {
    for i := 0; i < IdLength; i++ {
        for j := 0; j < 8; j++ {
            if (node[i]>>uint8(7-j))&0x1 != 0 {
                return i*8 + j
            }
        }
    }
    return IdLength*8 - 1
}