Click here to Skip to main content
14,739,223 members
Articles » Languages » C# » General
Posted 12 Apr 2012

Tagged as


5 bookmarked

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

Rate me:
Please Sign up or sign in to vote.
5.00/5 (6 votes)
12 Apr 2012CPOL
If you haven't heard of AI Memo 239, then you need to have a look at it. It is an MIT memo from 1972 containing "clever code" and such like. Some of it is absolutely beautiful!


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: - I won't upload it to Codeproject because I am not sure what it's copyright status is. 


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]
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
AND A,[070707,,070707]
IDIVI A,77             ;casting out 63.'s


Original version


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Wales Wales
Born at an early age, he grew older. At the same time, his hair grew longer, and was tied up behind his head.
Has problems spelling the word "the".
Invented the portable cat-flap.
Currently, has not died yet. Or has he?

Comments and Discussions

SuggestionIt's clearer when using type long Pin
Matt T Heffron12-Apr-12 9:19
professionalMatt T Heffron12-Apr-12 9:19 
GeneralRe: It's clearer when using type long Pin
OriginalGriff12-Apr-12 9:33
mveOriginalGriff12-Apr-12 9:33 
GeneralRe: It's clearer when using type long Pin
OriginalGriff12-Apr-12 23:55
mveOriginalGriff12-Apr-12 23:55 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.