Counting the number of set bits in a number
<p>The problem statement is: </p>

<p>Write an efficient program to count number of 1s in binary representation of an integer.</p>

<p>I found a post on this problem <a href="http://www.geeksforgeeks.org/count-set-bits-in-an-integer/" rel="nofollow">here</a> which outlines multiple solutions which run in log(n) time including Brian Kernigan's algorithm and the gcc <code>__builtin_popcount()</code> method.</p>

<p>One solution that wasn't mentioned was the python method: <code>bin(n).count("1")</code> 
which also achieves the same effect. Does this method also run in log n time?</p>

<p>Let's say you are trying to count the number of set bits of <code>n</code>. On <em>Python</em> typical implementations, <code>bin</code> will compute the binary representation in <code>O(log n)</code> time and <code>count</code> will go through the string, therefore resulting in an overall <code>O(log n)</code> complexity.</p>

<p>However, note that usually, the input parameter of algorithms is the "size" of the input. When you work with integers, this corresponds to their logarithm. That's why the current algorithm is said to have a <em>linear</em> complexity (the variable is <code>m = log n</code>, and the complexity <code>O(m)</code>).</p>

python algorithm bit-manipulation