Mercurial > louis > peeves
changeset 4:9748b64edb26
Add the bit count exercise
author | Louis Opter <kalessin@kalessin.fr> |
---|---|
date | Sat, 13 Jul 2013 19:47:11 -0700 |
parents | 1f4c37678f69 |
children | 7f981c321063 |
files | arrays/bit_count/bit_count.c arrays/bit_count/hints.rst arrays/bit_count/question.rst |
diffstat | 3 files changed, 46 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/arrays/bit_count/bit_count.c Sat Jul 13 19:47:11 2013 -0700 @@ -0,0 +1,37 @@ +#include <stdio.h> +#include <stdlib.h> + +/* + * There is different solutions but this one is simple and easy to remember + * (it's very similar to !(a & (a - 1)) used to check if a is a power of two). + * If you want to look smart, say that this solution is perfect for embedded + * systems. + * + * Another simple one, more optimized, is to have a lookup table that gives you + * the number of 1 bit in each integer for integers from 0 to 255 (or 0 to + * 2**16 - 1). + */ + +unsigned int +bit_count(const unsigned char *a, size_t n) +{ + unsigned int c = 0; + + while (n--) + for (unsigned char v = a[n]; v; v &= v - 1) + c++; + + return c; +} + +int +main(void) +{ + int a[] = { 1, 2, 3, 4 }; + int b = 42; + + printf("%d\n", bit_count((unsigned char *)a, sizeof(a))); + printf("%d\n", bit_count((unsigned char *)&b, sizeof(b))); + + return 0; +}