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

        /// <summary>
        /// Count the number of one bits in a value
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        private int CountOneBits(int value)
            {
            long temp = value - ((value >> 1) & 0xDB6DB6DB) - ((value >> 2) & 0x49249249);
            return (int) (((temp + (temp >> 3)) & 0xC71C71C7) % 63);
            }
        /// <summary>
        /// Count the number of zero bits in a value
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        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]      ;or MOVE B,A then LSH B,-1
        AND B,[333333,,333333]
        SUB A,B
        LSH B,-1
        AND B,[333333,,333333]
        SUBB A,B               ;each octal digit is replaced by number of 1's in it
        LSH B,-3
        ADD A,B
        AND A,[070707,,070707]
        IDIVI A,77             ;casting out 63.'s

History

Original version

A C# implementation of AI MEMO 239, Item 169- Count the one bits in a number