coding-exercises/bits_counter_methods.c at master · MIT-EPROM/coding-exercises · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>

unsigned int bits_counter_v0(unsigned int x) {
    unsigned int count = 0;
    while ( x != 0 ) {
        // If odd, add 1
        count += (x % 2 == 0) ? 0 : 1;
        x >>= 1;
    }

    return count;
}

unsigned int bits_counter_v1(unsigned int x) {
    unsigned int count = 0;
    while ( x != 0 ) {
        // If least-significant bit is 1, add 1
        count += (x & 1) ? 1 : 0;
        x >>= 1;
    }

    return count;
}

unsigned int bits_counter_v2(unsigned int x) {
    unsigned int count = 0;
    // "Hashmap" of the values for least significant 4 bits
    unsigned int int_to_bits_count[16] = {
        0, 1, 1, 2, // 0=00, 1=01, 2=10, 3=11
        1, 2, 2, 3, // 4=100, 5=101, 6=110, 7=111
        1, 2, 2, 3, // 8=1000, 9=1001, 10=1010, 11=1011
        2, 3, 3, 4  // 12=1100, 13=1101, 14=1110, 15=1111
    };

    while ( x != 0 ) {
        // Add the bits count of least significant 4 bits
        count += int_to_bits_count[ x & 15 ];
        x >>= 4;
    }

    return count;
}

unsigned int bits_counter_v3(unsigned int x) {
    unsigned int result = 0;
    // strip one set bit per iteration
    while (x != 0) {
        x &= x - 1;
        result++;
    }
    return result;
}

// Counting bits set in Parallel
unsigned int bits_counter_v4(unsigned int x) {
    // count bits of each 2-bit chunk
    x  = x - ((x >> 1) & 0x55555555);
    // count bits of each 4-bit chunk
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    // count bits of each 8-bit chunk
    x = x + (x >> 4);
    // mask out junk
    x &= 0xF0F0F0F;
    // add all four 8-bit chunks
    return (x * 0x01010101) >> 24;
}

int main(int argc, char** argv)
{
    int input;

    // Check the Input
	if ( argc == 2 ) input = atoi(argv[1]); else return (1);

	printf("--- BITS COUNTER METHODS ---\n");
	printf("bits_counter_v0(%d) = %d\n", input, bits_counter_v0((unsigned int)input));

	printf("bits_counter_v1(%d) = %d\n", input, bits_counter_v1((unsigned int)input));

	printf("bits_counter_v2(%d) = %d\n", input, bits_counter_v2((unsigned int)input));

    printf("bits_counter_v3(%d) = %d\n", input, bits_counter_v3((unsigned int)input));

    printf("bits_counter_v4(%d) = %d\n", input, bits_counter_v4((unsigned int)input));
	printf("----------------------------\n\n");

	return (0);
}