算法题（计算从1到n的所有数字中的总置位位数） _关闭最右边的设置位

本文概述给定正整数n, 以二进制表示形式表示从1到n的所有数字的置位位数。
例子：

Input: n = 3 Output:4Input: n = 6 Output: 9Input: n = 7 Output: 12Input: n = 8 Output: 13

资料来源：亚马逊面试问题
方法1(简单)
一个简单的解决方案是运行一个从1到n的循环, 并对从1到n的所有数字中的设置位计数进行求和。
C ++

// A simple program to count set bits // in all numbers from 1 to n. #include < stdio.h> // A utility function to count set bits // in a number x unsigned int countSetBitsUtil(unsigned int x); // Returns count of set bits present in all // numbers from 1 to n unsigned int countSetBits(unsigned int n) { int bitCount = 0; // initialize the resultfor ( int i = 1; i < = n; i++) bitCount += countSetBitsUtil(i); return bitCount; }// A utility function to count set bits // in a number x unsigned int countSetBitsUtil(unsigned int x) { if (x < = 0) return 0; return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2); }// Driver program to test above functions int main() { int n = 4; printf ( "Total set bit count is %d" , countSetBits(n)); return 0; }

Java

// A simple program to count set bits // in all numbers from 1 to n.class GFG{// Returns count of set bits present //in all numbers from 1 to n static int countSetBits( int n) { // initialize the result int bitCount = 0 ; for ( int i = 1 ; i < = n; i++) bitCount += countSetBitsUtil(i); return bitCount; }// A utility function to count set bits // in a number x static int countSetBitsUtil( int x) { if (x < = 0 ) return 0 ; return (x % 2 == 0 ? 0 : 1 ) + countSetBitsUtil(x / 2 ); }// Driver program public static void main(String[] args) { int n = 4 ; System.out.print( "Total set bit count is " ); System.out.print(countSetBits(n)); } }// This code is contributed by // Smitha Dinesh Semwal

Python3

# A simple program to count set bits # in all numbers from 1 to n.# Returns count of set bits present in all # numbers from 1 to n def countSetBits(n):# initialize the result bitCount = 0 for i in range ( 1 , n + 1 ): bitCount + = countSetBitsUtil(i)return bitCount# A utility function to count set bits # in a number x def countSetBitsUtil(x):if (x < = 0 ): return 0 return ( 0 if int (x % 2 ) = = 0 else 1 ) +countSetBitsUtil( int (x / 2 ))# Driver program if __name__ = = '__main__' : n = 4 print ( "Total set bit count is" , countSetBits(n))# This code is contributed by # Smitha Dinesh Semwal

// A simple C# program to count set bits // in all numbers from 1 to n. using System; class GFG { // Returns count of set bits present // in all numbers from 1 to n static int countSetBits( int n) { // initialize the result int bitCount = 0; for ( int i = 1; i < = n; i++) bitCount += countSetBitsUtil(i); return bitCount; }// A utility function to count set bits // in a number x static int countSetBitsUtil( int x) { if (x < = 0) return 0; return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2); }// Driver program public static void Main() { int n = 4; Console.Write( "Total set bit count is " ); Console.Write(countSetBits(n)); } }// This code is contributed by Sam007

的PHP

< ?php // A simple program to count set bits // in all numbers from 1 to n.// Returns count of set bits present // in all numbers from 1 to n function countSetBits( $n ) { $bitCount = 0; // initialize the resultfor ( $i = 1; $i < = $n ; $i ++) $bitCount += countSetBitsUtil( $i ); return $bitCount ; }// A utility function to count // set bits in a number x function countSetBitsUtil( $x ) { if ( $x < = 0) return 0; return ( $x % 2 == 0 ? 0 : 1) + countSetBitsUtil( $x / 2); }// Driver Code $n = 4; echo "Total set bit count is " . countSetBits( $n ); // This code is contributed by ChitraNayal ?>

输出如下：

Total set bit count is 5

【算法题（计算从1到n的所有数字中的总置位位数）】时间复杂度：O(nLogn)
方法2(比方法1简单高效)
如果我们从距离i的最右边观察到位, 则在垂直序列中2 ^ i位置后位会反转。
例如n = 5;
0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
观察最右边的位(i = 0), 这些位在(2 ^ 0 = 1)之后翻转
观察最右边的第三位(i = 2), 这些位在(2 ^ 2 = 4)之后被翻转
因此, 我们可以垂直方式对位进行计数, 以便在第i个最右边的位置, 在2 ^ i次迭代后, 位将被翻转；
C ++

#include < bits/stdc++.h> using namespace std; // Function which counts set bits from 0 to n int countSetBits( int n) { int i = 0; // ans store sum of set bits from 0 to n int ans = 0; // while n greater than equal to 2^i while ((1 < < i) < = n) {// This k will get flipped after // 2^i iterations bool k = 0; // change is iterator from 2^i to 1 int change = 1 < < i; // This will loop from 0 to n for // every bit position for ( int j = 0; j < = n; j++) {ans += k; if (change == 1) { k = !k; // When change = 1 flip the bit change = 1 < < i; // again set change to 2^i } else { change--; } }// increment the position i++; }return ans; }// Main Function int main() { int n = 17; cout < < countSetBits(n) < < endl; return 0; }

Java

public class GFG {// Function which counts set bits from 0 to n static int countSetBits( int n) { int i = 0 ; // ans store sum of set bits from 0 to n int ans = 0 ; // while n greater than equal to 2^i while (( 1 < < i) < = n) {// This k will get flipped after // 2^i iterations boolean k = false ; // change is iterator from 2^i to 1 int change = 1 < < i; // This will loop from 0 to n for // every bit position for ( int j = 0 ; j < = n; j++) {if (k == true ) ans += 1 ; else ans += 0 ; if (change == 1 ) {// When change = 1 flip the bit k = !k; // again set change to 2^i change = 1 < < i; } else { change--; } }// increment the position i++; }return ans; }// Driver program public static void main(String[] args) { int n = 17 ; System.out.println(countSetBits(n)); } }// This code is contributed by Sam007.

Python3

# Function which counts set bits from 0 to n def countSetBits(n) : i = 0# ans store sum of set bits from 0 to n ans = 0# while n greater than equal to 2^i while (( 1 < < i) < = n) :# This k will get flipped after # 2^i iterations k = 0# change is iterator from 2^i to 1 change = 1 < < i# This will loop from 0 to n for # every bit position for j in range ( 0 , n + 1 ) : ans + = kif change = = 1 :#When change = 1 flip the bit k = not k# again set change to 2^i change = 1 < < ielse : change - = 1# increment the position i + = 1return ans# Driver code if __name__ = = "__main__" :n = 17 print (countSetBits(n))# This code is contributed by ANKITRAI1

using System; class GFG { static int countSetBits( int n) { int i = 0; // ans store sum of set bits from 0 to n int ans = 0; // while n greater than equal to 2^i while ((1 < < i) < = n) {// This k will get flipped after // 2^i iterations bool k = false ; // change is iterator from 2^i to 1 int change = 1 < < i; // This will loop from 0 to n for // every bit position for ( int j = 0; j < = n; j++) {if (k == true ) ans += 1; else ans += 0; if (change == 1) {// When change = 1 flip the bit k = !k; // again set change to 2^i change = 1 < < i; } else { change--; } }// increment the position i++; }return ans; }// Driver program static void Main() { int n = 17; Console.Write(countSetBits(n)); } }// This code is contributed by Sam007

的PHP

< ?php // Function which counts // set bits from 0 to n function countSetBits( $n ) { $i = 0; // ans store sum of set // bits from 0 to n $ans = 0; // while n greater than // equal to 2^i while ((1 < < $i ) < = $n ) {// This k will get flipped // after 2^i iterations $k = 0; // change is iterator // from 2^i to 1 $change = 1 < < $i ; // This will loop from 0 to n // for every bit position for ( $j = 0; $j < = $n ; $j ++) { $ans += $k ; if ( $change == 1) { // When change = 1 flip // the bit $k = ! $k ; // again set change to 2^i $change = 1 < < $i ; } else { $change --; } }// increment the position $i ++; }return $ans ; }// Driver code $n = 17; echo (countSetBits( $n )); // This code is contributed by Smitha ?>

输出如下：

35

时间复杂度：O(k * n)
其中k =表示数字n的位数
k < = 64
方法3(整rick)
如果输入数的形式为2 ^ b -1, 例如1、3、7、15等, 则设置位数为b * 2 ^(b-1)。这是因为对于从0到(2 ^ b)-1的所有数字, 如果对列表进行补充和翻转, 则最终将得到相同的列表(位的一半打开, 一半关闭)。
如果数字没有全部设置位, 则某个位置m是最左边的设置位的位置。该位置的置位位数为n –(1 < < m)+1。其余的置位分为两部分：
1)(m-1)中的位向下定位到最左边的位变为0的点, 并且
2)该点以下的2 ^(m-1)数是上面的封闭形式。
一个简单的方法是考虑数字6：

0|0 0 0|0 1 0|1 0 0|1 1 -|-- 1|0 0 1|0 1 1|1 0

最左边的置1位在位置2(位置从0开始)。如果我们掩盖掉剩下的是2(最后一行右侧的" 1 0"。)那么第二个位置(左下方的框)的位数是3(即2 + 1) 。 0-3(上面右上方的框)中的设置位是2 * 2 ^(2-1)=4。右下角的框是我们尚未计数的剩余位, 是设置的数量可以递归计算最多2个数字(右下方框中最后一个条目的值)的位数。
C ++

#include < bits/stdc++.h> // A O(Logn) complexity program to count // set bits in all numbers from 1 to n using namespace std; /* Returns position of leftmost set bit. The rightmost position is considered as 0 */ unsigned int getLeftmostBit( int n) { int m = 0; while (n > 1) { n = n > > 1; m++; } return m; } /* Given the position of previous leftmost set bit in n (or an upper bound on leftmost position) returns the new position of leftmost set bit in n */ unsigned int getNextLeftmostBit( int n, int m) { unsigned int temp = 1 < < m; while (n < temp) { temp = temp > > 1; m--; } return m; } // The main recursive function used by countSetBits() unsigned int _countSetBits(unsigned int n, int m); // Returns count of set bits present in // all numbers from 1 to n unsigned int countSetBits(unsigned int n) { // Get the position of leftmost set // bit in n. This will be used as an // upper bound for next set bit function int m = getLeftmostBit(n); // Use the position return _countSetBits(n, m); } unsigned int _countSetBits(unsigned int n, int m) { // Base Case: if n is 0, then set bit // count is 0 if (n == 0) return 0; /* get position of next leftmost set bit */ m = getNextLeftmostBit(n, m); // If n is of the form 2^x-1, i.e., if n // is like 1, 3, 7, 15, 31, .. etc, // then we are done. // Since positions are considered starting // from 0, 1 is added to m if (n == ((unsigned int )1 < < (m + 1)) - 1) return (unsigned int )(m + 1) * (1 < < m); // update n for next recursive call n = n - (1 < < m); return (n + 1) + countSetBits(n) + m * (1 < < (m - 1)); } // Driver code int main() { int n = 17; cout< < "Total set bit count is " < < countSetBits(n); return 0; } // This code is contributed by rathbhupendra

// A O(Logn) complexity program to count // set bits in all numbers from 1 to n #include < stdio.h> /* Returns position of leftmost set bit. The rightmost position is considered as 0 */ unsigned int getLeftmostBit( int n) { int m = 0; while (n > 1) { n = n > > 1; m++; } return m; }/* Given the position of previous leftmost set bit in n (or an upper bound on leftmost position) returns the new position of leftmost set bit in n*/ unsigned int getNextLeftmostBit( int n, int m) { unsigned int temp = 1 < < m; while (n < temp) { temp = temp > > 1; m--; } return m; }// The main recursive function used by countSetBits() unsigned int _countSetBits(unsigned int n, int m); // Returns count of set bits present in // all numbers from 1 to n unsigned int countSetBits(unsigned int n) { // Get the position of leftmost set // bit in n. This will be used as an // upper bound for next set bit function int m = getLeftmostBit(n); // Use the position return _countSetBits(n, m); }unsigned int _countSetBits(unsigned int n, int m) { // Base Case: if n is 0, then set bit // count is 0 if (n == 0) return 0; /* get position of next leftmost set bit */ m = getNextLeftmostBit(n, m); // If n is of the form 2^x-1, i.e., if n // is like 1, 3, 7, 15, 31, .. etc, // then we are done. // Since positions are considered starting // from 0, 1 is added to m if (n == ((unsigned int )1 < < (m + 1)) - 1) return (unsigned int )(m + 1) * (1 < < m); // update n for next recursive call n = n - (1 < < m); return (n + 1) + countSetBits(n) + m * (1 < < (m - 1)); }// Driver program to test above functions int main() { int n = 17; printf ( "Total set bit count is %d" , countSetBits(n)); return 0; }

Java

// Java A O(Logn) complexity program to count // set bits in all numbers from 1 to n import java.io.*; class GFG {/* Returns position of leftmost set bit. The rightmost position is considered as 0 */ static int getLeftmostBit( int n) { int m = 0 ; while (n > 1 ) { n = n > > 1 ; m++; } return m; } /* Given the position of previous leftmost set bit in n (or an upper bound on leftmost position) returns the new position of leftmost set bit in n */ static int getNextLeftmostBit( int n, int m) { int temp = 1 < < m; while (n < temp) { temp = temp > > 1 ; m--; } return m; } // The main recursive function used by countSetBits() // Returns count of set bits present in // all numbers from 1 to n static int countSetBits( int n) { // Get the position of leftmost set // bit in n. This will be used as an // upper bound for next set bit function int m = getLeftmostBit(n); // Use the position return countSetBits(n, m); } static int countSetBits( int n, int m) { // Base Case: if n is 0, then set bit // count is 0 if (n == 0 ) return 0 ; /* get position of next leftmost set bit */ m = getNextLeftmostBit(n, m); // If n is of the form 2^x-1, i.e., if n // is like 1, 3, 7, 15, 31, .. etc, // then we are done. // Since positions are considered starting // from 0, 1 is added to m if (n == (( int ) 1 < < (m + 1 )) - 1 ) return ( int )(m + 1 ) * ( 1 < < m); // update n for next recursive call n = n - ( 1 < < m); return (n + 1 ) + countSetBits(n) + m * ( 1 < < (m - 1 )); } // Driver code public static void main (String[] args) {int n = 17 ; System.out.println ( "Total set bit count is " + countSetBits(n)); } }// This code is contributed by ajit..

Python3

# A O(Logn) complexity program to count # set bits in all numbers from 1 to n""" /* Returns position of leftmost set bit. The rightmost position is considered as 0 */ """ def getLeftmostBit(n):m = 0 while (n > 1 ) :n = n > > 1 m + = 1return m""" /* Given the position of previous leftmost set bit in n (or an upper bound on leftmost position) returns the new position of leftmost set bit in n */ """ def getNextLeftmostBit(n, m) :temp = 1 < < m while (n < temp) : temp = temp > > 1 m - = 1return m# The main recursive function used by countSetBits() # def _countSetBits(n, m)# Returns count of set bits present in # all numbers from 1 to n def countSetBits(n) :# Get the position of leftmost set # bit in n. This will be used as an # upper bound for next set bit function m = getLeftmostBit(n)# Use the position return _countSetBits(n, m)def _countSetBits(n, m) :# Base Case: if n is 0, then set bit # count is 0 if (n = = 0 ) : return 0# /* get position of next leftmost set bit */ m = getNextLeftmostBit(n, m)# If n is of the form 2^x-1, i.e., if n # is like 1, 3, 7, 15, 31, .. etc, # then we are done. # Since positions are considered starting # from 0, 1 is added to m if (n = = ( 1 < < (m + 1 )) - 1 ) : return ((m + 1 ) * ( 1 < < m))# update n for next recursive call n = n - ( 1 < < m) return (n + 1 ) + countSetBits(n) + m * ( 1 < < (m - 1 ))# Driver code n = 17 print ( "Total set bit count is" , countSetBits(n))# This code is contributed by rathbhupendra

// C# A O(Logn) complexity program to count // set bits in all numbers from 1 to n using System; class GFG {/* Returns position of leftmost set bit. The rightmost position is considered as 0 */ static int getLeftmostBit( int n) { int m = 0; while (n > 1) { n = n > > 1; m++; } return m; } /* Given the position of previous leftmost set bit in n (or an upper bound on leftmost position) returns the new position of leftmost set bit in n */ static int getNextLeftmostBit( int n, int m) { int temp = 1 < < m; while (n < temp) { temp = temp > > 1; m--; } return m; } // The main recursive function used by countSetBits() // Returns count of set bits present in // all numbers from 1 to n static int countSetBits( int n) { // Get the position of leftmost set // bit in n. This will be used as an // upper bound for next set bit function int m = getLeftmostBit(n); // Use the position return countSetBits(n, m); } static int countSetBits( int n, int m) { // Base Case: if n is 0, // then set bit count is 0 if (n == 0) return 0; /* get position of next leftmost set bit */ m = getNextLeftmostBit(n, m); // If n is of the form 2^x-1, i.e., if n // is like 1, 3, 7, 15, 31, .. etc, // then we are done. // Since positions are considered starting // from 0, 1 is added to m if (n == (( int )1 < < (m + 1)) - 1) return ( int )(m + 1) * (1 < < m); // update n for next recursive call n = n - (1 < < m); return (n + 1) + countSetBits(n) + m * (1 < < (m - 1)); } // Driver code static public void Main () { int n = 17; Console.Write( "Total set bit count is " + countSetBits(n)); } }// This code is contributed by Tushil.

输出如下：

Total set bit count is 35

时间复杂度：O(Logn)。从实现的第一眼看, 时间复杂度看起来更多。但是, 如果我们仔细研究一下, 则将对n中的所有0位执行getNextLeftmostBit()的while循环内的语句。并且执行递归的次数小于或等于n中的设置位。换句话说, 如果控件进入getNextLeftmostBit()的while循环内部, 则它将跳过递归的许多位。
感谢agatsu和IC提出此解决方案。
这是另一种建议的解决方案皮尤什·卡普尔(Piyush Kapoor).
一个简单的解决方案, 使用以下事实：对于第i个最低有效位, 答案为

(N/2^i)*2^(i-1)+ X

其中

X = N%(2^i)-(2^(i-1)-1)

iff

N%(2^i)> =(2^(i-1)-1)

int getSetBitsFromOneToN( int N){ int two = 2, ans = 0; int n = N; while (n){ ans += (N/two)*(two> > 1); if ((N& (two-1)) > (two> > 1)-1) ans += (N& (two-1)) - (two> > 1)+1; two < < = 1; n > > = 1; } return ans; }

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。