13,357,514 members (36,238 online)
Tip/Trick
alternative version

#### Stats

8.4K views
5 bookmarked
Posted 12 Apr 2012

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

, 12 Apr 2012
 Rate this:
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
AND A,[070707,,070707]
IDIVI A,77             ;casting out 63.'s
```

Original version

## Share

 CEO 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?

## You may also be interested in...

 Pro Pro

 First Prev Next
 It's clearer when using type long Matt T Heffron12-Apr-12 9:19 Matt T Heffron 12-Apr-12 9:19
 Re: It's clearer when using type long OriginalGriff12-Apr-12 9:33 OriginalGriff 12-Apr-12 9:33
 Re: It's clearer when using type long OriginalGriff12-Apr-12 23:55 OriginalGriff 12-Apr-12 23:55
 Last Visit: 31-Dec-99 19:00     Last Update: 23-Jan-18 18:16 Refresh 1