Count Ones

binary_counts_with_fingersHere is a simple task. Given an array of 10,000 random unsigned short integers (16-bit values) count the number of bits set to one (1). In the following example we have an array of two (2) unsigned shorts:

41344 1010000110000000

58520 1110010010011000

The first number 41,344 contains 4 ones and the second value 58,520 contains 7 ones for a total of (4 + 7) = 11 ones.

As with any other problem, different people would come up with different approaches. On one end one may come with a brute force approach. On the other, one may come up with an elegant solution. We should also consider the variations in the goal for this problem. For example, we might be asked to find out the number of 0s in the fourth binary digit of all entries in the array.brute_force

Let’s start with a brute force approach. I will write the solution using the Java programming language. As you are aware, Java does not support unsigned or short digits. As I looked at the problem, C/C++ came to mind. Those languages are relatively fast and provide support for the unsigned short data type. Perhaps a quick implementation in C to collect some data might not be a bad idea.

I have included in the same source code the non-brute force approach to solve the challenge. Let’s start with a run, some comments and the actual code.

>>> N: 100000

<<< ones: 800705 duration: 11 ms

<<< ones: 800705 duration: 3 ms

einstein_eyesThe code starts by prompting for the number of entries in the array. I decided not to hard code it so we could be able to experiment with different counts. It is always important to understand what happens when the number of elements in an algorithm changes. It might be that the number of unsigned short integers is relatively small (e.g., 1,000) and the execution time is so close (e.g., <= 1 ms) that spending time optimizing the code might be better applied in other parts of the system.

When testing code, always run the test 5 times. Drop the slowest and fastest times and then average the remaining 3 times. The code for the Count Ones program follows:

package john.tests;

import java.util.Random;

import java.util.Scanner;

public class Solution {

static int    countOnes(int val) {

int count     = 0;

for (int i = 0; i < 16; i++) {

if ((val & 1) == 1) {

count++;

}

val = val >> 1;

}

return count;

}

static int[] buildTable() {

int[] table   = new int[256];

for (int i = 0; i < table.length; i++) {

table[i] = countOnes(i);

//                   System.out.println(“<<< table[” + i + “]: “+ table[i]);

}

return table;

}

public static void main(String[] args) {

final int maxNum     = (256 * 256 – 1);

Scanner sc                 = new Scanner(System.in);

Random rand          = new Random(System.currentTimeMillis());

int    ones                 = 0;

// **** create an array of short integers (integers) with N random values ****

System.out.print(“>>> N: “);

int N         = sc.nextInt();

int[] arr     = new int[N];

// **** fill the array with random values ****

for (int n = 0; n < N; n++) {

arr[n] = rand.nextInt(maxNum);

//                   System.out.println(arr[n] + ” ” + (String.format(“%16s”, Integer.toBinaryString(arr[n])).replace(” “, “0”)) );

}

// **** ****

sc.close();

// **** start time ****

long startTime = System.currentTimeMillis();

// **** brute force approach ****

for (int n = 0; n < N; n++) {

ones += countOnes(arr[n]);

}

// **** end time ****

long endTime = System.currentTimeMillis();

// **** ****

System.out.println(“<<< ones: ” + ones + ” duration: ” + (endTime – startTime) + ” ms”);

// **** build table with counts ****

int[] table = buildTable();

// **** start time ****

startTime = System.currentTimeMillis();

// **** ****

ones = 0;

for (int n = 0; n < N; n++) {

ones += table[arr[n] & 0x00ff];

ones += table[(arr[n] >> 8) & 0x00ff];

}

// **** end time ****

endTime = System.currentTimeMillis();

// **** ****

System.out.println(“<<< ones: ” + ones + ” duration: ” + (endTime – startTime) + ” ms”);

}

}

Some output lines have been commented out. I used them to get additional information while I was writing the code. When done I tend to delete some and keep a few lines for the time when someone (including myself) will go back to enhance the code.

The results tend to indicate that the optimized software is about 4 times faster than the brute force approach. The results also indicate that about half of the bits 100,000 * 16 / 2 are ones. That is as expected because we are using a pseudo random generator and the likelihood of having one or zero is about 50%.

The code starts by prompting the user for the number of entries in the array. The array is then populated with numbers in the range [0 :  256 * 256 – 1].

The brute force approach invokes the countOnes() method. A value from the array passed to it is anded and shifted once so we are able to count the number of bits set to one. The count is returned to the caller.shorter_time

In the second approach we build a table of bytes with 256 entries. Each entry holds the count of ones for each possible byte. The table starts with 0x00 (0 ones) and ends with 0xff (8 ones). We will use the table in the next and final step.

The main program then traverses the original set of unsigned short integers and maps the number of ones on the lower and then upper byte. That eliminates shifting the value.

The results produced for both approaches using the same array come up with the same value. This is another useful check to verify that if we change or add a new approach it should produce the same counts but hopefully better (smaller) execution times.

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *