## Introduction

AI Memo 239 presented a selection of hack, tips and "clever code" which could be used within MIT for general purpose - if you like, it was the forerunner of Tips and Tricks here. It is also known as MIT HAKEM and the full text can be found here: http://home.pipeline.com/~hbaker1/hakmem/hakmem.html - I won't upload it to Codeproject because I am not sure what it's copyright status is.

## Background

This started with a QA question, about identifying powers of two - I vaguely remembered seeing something about counting the number of "one" bits in MIT HAKEM, and wondered if I could find and use that. Oh yes!

The algorithm is pretty simple, it needs no loops and (in PDP6/10 machine code) is only ten instructions long! All I have done is implement it in C#.

## The code

private int CountOneBits(int value)
{
long temp = value - ((value >> 1) & 0xDB6DB6DB) - ((value >> 2) & 0x49249249);
return (int) (((temp + (temp >> 3)) & 0xC71C71C7) % 63);
}
private int CountZeroBits(int value)
{
return CountOneBits(~value);
}

## How it works

Think about Octal: each digit has three bits.
`value = 4x+2y+z`

, where `x`

, `y`

and `z`

are either zero or one. If we shift value right 1 bit, we have `2x+y`

. Subtracting this from the original gives `2x+y+z`

. If we right-shift the original value by two bits, we get `x`

, and so with another subtraction we have `x+y+z`

, which is the number of bits in the original number. All we need to do is extend this to the number of octal digits in the number.
First, we use the above to generate a temporary value - the number of one bits in each octal digit, as an octal digit.
Then, we just add adjacent pairs of octal digits together, and get the remainder modulus 63 - which is the digits count.
Trust me, I didn't think of this, it's a very clever idea - it would also be a lot more obvious if C# has an octal notation, instead of having to use hex!
The magic numbers in the code above are a lot clearer in octal:

0xdb6db6db == 33333333333 octal
0x49249249 == 11111111111 octal
0xC71C71C7 == 30707070707 octal

## PDP Code

LDB B,[014300,,A]
AND B,[333333,,333333]
SUB A,B
LSH B,-1
AND B,[333333,,333333]
SUBB A,B
LSH B,-3
ADD A,B
AND A,[070707,,070707]
IDIVI A,77

## History

Original version