Click here to Skip to main content
Click here to Skip to main content

Tagged as

Go to top

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

, 12 Apr 2012
Rate this:
Please Sign up or sign in to vote.
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!

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

License

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

Share

About the Author

OriginalGriff
CEO
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?
Follow on   Google+

Comments and Discussions

 
SuggestionIt's clearer when using type long [modified] PinmemberMatt T Heffron12-Apr-12 8:19 
GeneralRe: It's clearer when using type long PinmvpOriginalGriff12-Apr-12 8:33 
GeneralRe: It's clearer when using type long PinmvpOriginalGriff12-Apr-12 22:55 

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

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

| Advertise | Privacy | Mobile
Web02 | 2.8.140916.1 | Last Updated 12 Apr 2012
Article Copyright 2012 by OriginalGriff
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid