本文概述
给定正整数n, 以二进制表示形式表示从1到n的所有数字的置位位数。
例子：
Input: n = 3
Output: 4
Input: n = 6
Output: 9
Input: n = 7
Output: 12
Input: 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 result
for ( 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 SemwalPython3
# 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 SemwalC#
// 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 result
for ( $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时间复杂度：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 + = k
if change = = 1 :
# When change = 1 flip the bit
k = not k
# again set change to 2^i
change = 1 << i
else :
change - = 1
# increment the position
i + = 1
return ans
# Driver code
if __name__ = = "__main__" :
n = 17
print (countSetBits(n))
# This code is contributed by ANKITRAI1C#
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 rathbhupendraC
// 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 + = 1
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 */
"""
def getNextLeftmostBit(n, m) :
temp = 1 << m
while (n < temp) :
temp = temp >> 1
m - = 1
return 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 rathbhupendraC#
// 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;
}如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
![从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1](https://www.lsbin.com/wp-content/themes/begin%20lts/img/loading.png)
