{"id":25888,"date":"2017-10-25T21:12:06","date_gmt":"2017-10-25T15:42:06","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25888"},"modified":"2017-10-25T21:12:06","modified_gmt":"2017-10-25T15:42:06","slug":"program-count-number-set-bits-big-array","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/program-count-number-set-bits-big-array\/","title":{"rendered":"Program to count number of set bits in an (big) array"},"content":{"rendered":"<p>Given an integer array of length N (an\u00a0arbitrarily\u00a0large number). How to count number of set bits in the array?<span id=\"more-11263\"><\/span><\/p>\n<p>The simple approach would be, create an efficient method to count set bits in a word (most prominent size, usually equal to bit length of processor), and add bits from individual elements of array.<\/p>\n<p>Various methods of counting set bits of an integer exists, see <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/1176\" target=\"_blank\" rel=\"noopener noreferrer\">this<\/a> for example. These methods run at best O(logN) where N is number of bits. Note that on a processor N is fixed, count\u00a0can be done in O(1) time on 32 bit machine irrespective of total set bits. Overall, the bits in array can be computed in O(n) time, where \u2018n\u2019 is array size.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>However, a table look up will be more efficient method when array size is large. Storing table look up that can handle 2<sup>32<\/sup> integers will be impractical.<\/p>\n<p>The following code illustrates simple program to count set bits in a randomly generated 64 K integer array. The idea is to generate a look up for first 256 numbers (one byte), and break every element of array at byte boundary. A meta program using C\/C++ preprocessor generates the look up table for counting set bits in a byte.<\/p>\n<p>The\u00a0mathematical\u00a0derivation behind meta program is evident from the following table (Add the column and row indices to get the number, then look into the table to get set bits in that number. For example, to get set bits in 10, it can be extracted from row named as 8 and column named as 2),<\/p>\n<pre> \u00a00, 1, 2, 3\r\n 0 - 0, 1, 1, 2 -------- GROUP_A(0)\r\n 4 - 1, 2, 2, 3 -------- GROUP_A(1)\r\n 8 - 1, 2, 2, 3 -------- GROUP_A(1)\r\n12 - 2, 3, 3, 4 -------- GROUP_A(2)\r\n16 - 1, 2, 2, 3 -------- GROUP_A(1)\r\n20 - 2, 3, 3, 4 -------- GROUP_A(2)\r\n24 - 2, 3, 3, 4 -------- GROUP_A(2)\r\n28 - 3, 4, 4, 5 -------- GROUP_A(3) ... so on<\/pre>\n<p>From the table, there is a patten emerging in multiples of 4, both in the table as well as in the group parameter. The sequence can be generalized as shown in the code.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Complexity:<\/strong><\/p>\n<p>All the operations takes O(1) except iterating over the array. The time complexity is O(n) where \u2018n\u2019 is size of array. Space complexity depends on the meta program that generates look up.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%23include%20%3Ctime.h%3E%0A%20%0A%2F*%20Size%20of%20array%2064%20K%20*%2F%0A%23define%20SIZE%20(1%20%3C%3C%2016)%0A%20%0A%2F*%20Meta%20program%20that%20generates%20set%20bit%20count%0A%20%20%20array%20of%20first%20256%20integers%20*%2F%0A%20%0A%2F*%20GROUP_A%20-%20When%20combined%20with%20META_LOOK_UP%0A%20%20%20generates%20count%20for%204\u00d74%20elements%20*%2F%0A%20%0A%23define%20GROUP_A(x)%20x%2C%20x%20%2B%201%2C%20x%20%2B%201%2C%20x%20%2B%202%0A%20%0A%2F*%20GROUP_B%20-%20When%20combined%20with%20META_LOOK_UP%0A%20%20%20generates%20count%20for%204x4x4%20elements%20*%2F%0A%20%0A%23define%20GROUP_B(x)%20GROUP_A(x)%2C%20GROUP_A(x%2B1)%2C%20GROUP_A(x%2B1)%2C%20GROUP_A(x%2B2)%0A%20%0A%2F*%20GROUP_C%20-%20When%20combined%20with%20META_LOOK_UP%0A%20%20%20generates%20count%20for%204x4x4x4%20elements%20*%2F%0A%20%0A%23define%20GROUP_C(x)%20GROUP_B(x)%2C%20GROUP_B(x%2B1)%2C%20GROUP_B(x%2B1)%2C%20GROUP_B(x%2B2)%0A%20%0A%2F*%20Provide%20appropriate%20letter%20to%20generate%20the%20table%20*%2F%0A%20%0A%23define%20META_LOOK_UP(PARAMETER)%20%5C%0A%20%20%20GROUP_%23%23PARAMETER(0)%2C%20%20%5C%0A%20%20%20GROUP_%23%23PARAMETER(1)%2C%20%20%5C%0A%20%20%20GROUP_%23%23PARAMETER(1)%2C%20%20%5C%0A%20%20%20GROUP_%23%23PARAMETER(2)%20%20%20%5C%0A%20%0Aint%20countSetBits(int%20array%5B%5D%2C%20size_t%20array_size)%0A%7B%0A%20%20%20int%20count%20%3D%200%3B%0A%20%0A%20%20%20%2F*%20META_LOOK_UP(C)%20-%20generates%20a%20table%20of%20256%20integers%20whose%0A%20%20%20%20%20%20sequence%20will%20be%20number%20of%20bits%20in%20i-th%20position%0A%20%20%20%20%20%20where%200%20%3C%3D%20i%20%3C%20256%0A%20%20%20*%2F%0A%20%0A%20%20%20%20%2F*%20A%20static%20table%20will%20be%20much%20faster%20to%20access%20*%2F%0A%20%20%20%20%20%20%20static%20unsigned%20char%20const%20look_up%5B%5D%20%3D%20%7B%20META_LOOK_UP(C)%20%7D%3B%0A%20%0A%20%20%20%20%2F*%20No%20shifting%20funda%20(for%20better%20readability)%20*%2F%0A%20%20%20%20unsigned%20char%20*pData%20%3D%20NULL%3B%0A%20%0A%20%20%20for(size_t%20index%20%3D%200%3B%20index%20%3C%20array_size%3B%20index%2B%2B)%0A%20%20%20%7B%0A%20%20%20%20%20%20%2F*%20It%20is%20fine%2C%20bypass%20the%20type%20system%20*%2F%0A%20%20%20%20%20%20pData%20%3D%20(unsigned%20char%20*)%26array%5Bindex%5D%3B%0A%20%0A%20%20%20%20%20%20%2F*%20Count%20set%20bits%20in%20individual%20bytes%20*%2F%0A%20%20%20%20%20%20count%20%2B%3D%20look_up%5BpData%5B0%5D%5D%3B%0A%20%20%20%20%20%20count%20%2B%3D%20look_up%5BpData%5B1%5D%5D%3B%0A%20%20%20%20%20%20count%20%2B%3D%20look_up%5BpData%5B2%5D%5D%3B%0A%20%20%20%20%20%20count%20%2B%3D%20look_up%5BpData%5B3%5D%5D%3B%0A%20%20%20%7D%0A%20%0A%20%20%20return%20count%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%2C%20generates%20table%20of%20random%2064%20K%20numbers%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20int%20index%3B%0A%20%20%20int%20random%5BSIZE%5D%3B%0A%20%0A%20%20%20%2F*%20Seed%20to%20the%20random-number%20generator%20*%2F%0A%20%20%20srand((unsigned)time(0))%3B%0A%20%0A%20%20%20%2F*%20Generate%20random%20numbers.%20*%2F%0A%20%20%20for(%20index%20%3D%200%3B%20index%20%3C%20SIZE%3B%20index%2B%2B%20)%0A%20%20%20%7B%0A%20%20%20%20%20%20random%5Bindex%5D%20%3D%20rand()%3B%0A%20%20%20%7D%0A%20%0A%20%20%20printf(%22Total%20number%20of%20bits%20%3D%20%25d%5Cn%22%2C%20countSetBits(random%2C%20SIZE))%3B%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Program to count number of set bits in an (big) array- Bit Algorithm &#8211; The simple approach would be, create an efficient method to count set bits in a word.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,79658,74852],"tags":[75083,75079,75879,75268,75111,75109,75884,75078,75091,75878,75084,75093,75270,75098,75886,74432,75281,73333,75089,75070,75897,75882,75883,75893,75104,75894,75896,75891,75881,75100,75086],"class_list":["post-25888","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-array","category-bit-algorithms","tag-bitwise-operations-in-c","tag-bitwise-operator-in-c","tag-bs-it","tag-bytes-table","tag-c-byte","tag-c-xor","tag-chacker","tag-clearbit","tag-counter-bit-set","tag-counter-set","tag-counting-bits","tag-cs-counter","tag-first-in-math-hack","tag-for-bit","tag-html-graphics","tag-integer-numbers","tag-magic-bit","tag-n-number-lookup","tag-nextbit","tag-number-counter","tag-number-sets","tag-population-counter","tag-powers-of-2","tag-python-bit","tag-set-bit","tag-set-count","tag-set-number","tag-two-bit-counter","tag-vbit","tag-word-bit","tag-xor-operator-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25888","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25888"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25888\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}