bit-twiddling.go

package main

import "fmt"

func roundUpToPow2(x uint64) uint64 {
	x--
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	x |= x >> 32
	x++
	return x
}

func countRightZeros(x uint64) uint {
	var c uint = 64
	x &= uint64(-int64(x))
	if x > 0 {
		c--
	}
	if (x & 0x00000000FFFFFFFF) > 0 {
		c -= 32
	}
	if (x & 0x0000FFFF0000FFFF) > 0 {
		c -= 16
	}
	if (x & 0x00FF00FF00FF00FF) > 0 {
		c -= 8
	}
	if (x & 0x0F0F0F0F0F0F0F0F) > 0 {
		c -= 4
	}
	if (x & 0x3333333333333333) > 0 {
		c -= 2
	}
	if (x & 0x5555555555555555) > 0 {
		c -= 1
	}
	return c
}


func main() {
	fmt.Println("val [ binary ] -> Next Power of 2 / Trailing Zeros")
	fmt.Println("------------------------")
	for i := uint64(0); i < 256; i++ {
		fmt.Printf("%03d [%08b] -> %v/%v\n", i, i, roundUpToPow2(i), countRightZeros(i))

	}
	test := []uint64{0xFFFFFFFFFFFFFFFF, 0xFFFFFFFF00000000, 0xFEDCBA986543210}
	for _, val := range test {
		fmt.Printf("%03d [%08b] -> %v/%v\n", val, val, roundUpToPow2(val), countRightZeros(val))
	}
}