Thursday, 9 February 2017

Bit Hacks in Go

Some time ago I wrote about little bit tweddlings in C, I, recently, have tried something similar in GO. It's not easy, for example bit shifts (>>) works only for unsigned integers and other differences. For now I reproduced and tested two things (both work on unsigned ints):  
Integer mean without casing an overflow and exponenation by binary decomposition.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func iexp(x uint32, n uint32) uint32 {
   if (n == 0) {
    return 1
   }
   var p, y uint32 
   y = 1;
   p = x;
   for {
    if (n & 1 != 0) {y = p*y}
     n >>= 1;
    if (n == 0) {return y}
     p *= p;
   }
  return 0
 }
Above is about 4 to 5 times faster than math.Pow from library.
Average:

1
2
3
func average(x uint32, y uint32) uint32 {
 return (x & y) + ((x ^ y) >> 1)
}

This time the adventage is not speed, but the fact, that we have the average without overflow (works,  for ex., for:, 2^32 - 1 and 2^32 - 1).  
That's it, code also on github, till the next time!

3 comments:

Piotr Lemanczyk said...

I tried same average function in C but i do not understand how is that faster. In assembler it seems that time would be similar if not same. See here for my results https://godbolt.org/g/CEmy2E

lion137 said...

Thanks for bringing this, my bad, I did't state it clear ('ve updated the post anyway), the trick in the average function is, that it won't overflow not speed.

Piotr Lemanczyk said...

Ok now I get it. The glitch in the division cause the overflow like here:
http://ideone.com/Xpt8dN