# 算法题：计算从1到n的所有数字中的总置位位数

2021年3月25日11:55:30 发表评论 348 次浏览

## 本文概述

``````Input: n = 3
Output:  4

Input: n = 6
Output: 9

Input: n = 7
Output: 12

Input: n = 8
Output: 13``````

## 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 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``````

## C#

``````// 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``

0 = 0000

1 = 0001

2 = 0010

3 = 0011

4 = 0100

5 = 0101

## 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 ANKITRAI1``````

## C#

``````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``

k <= 64

1)(m-1)中的位向下定位到最左边的位变为0的点, 并且

2)该点以下的2 ^(m-1)数是上面的封闭形式。

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

## 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``````

## C

``````// 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 rathbhupendra``````

## C#

``````// 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``

``(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;
}`````` 