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

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

本文概述

给定正整数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 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

时间复杂度: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 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

时间复杂度: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

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

时间复杂度: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;
}

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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: