二进制中 1 的个数（C++ 和 Python 实现）

/*
* Author: klchang
* Date: 2017.12.16
* Description: Compute the number of 1 in the binary representation of an integer.
*/

#include <iostream>

#define INT_BITS 32

// Generic method: bitwise and operation with a number that has only one 1 in binary.
int numberOf_1_InBinary_Generic(int i)
{
    int count = 0;
    int shiftCount = 0;

    while (i && shiftCount < INT_BITS)
    {
        if (i & 1) {
            ++ count;
        }
        i = i >> 1;
        ++ shiftCount;
    }

    return count;
}

// Fast method: bitwise and operation between integer i and (i-1).
int numberOf_1_InBinary_Fast(int i)
{
    int count = 0;
    while (i)
    {
        std::cout << "iter " << count << ": " << i << std::endl;
        i = i & (i - 1);
        count ++;
    }

    return count;
}

void unitest()
{
    int data[] = {-5, 0, 5};

    std::cout << "---------------------- Generic Method -----------------------"  << std::endl;
    for (int i = 0; i < 3; ++i)
        std::cout << "The number of 1 in the binary representation of " << data[i] << " is "
                  << numberOf_1_InBinary_Generic(data[i]) << ".
" << std::endl;

    std::cout << "----------------------- Fast Method --------------------------"  << std::endl;
    for (int i = 0; i < 3; ++i)
        std::cout << "The number of 1 in the binary representation of " << data[i] << " is "
                  << numberOf_1_InBinary_Fast(data[i]) << ".
" << std::endl;
}

int main()
{
    unitest();

    return 0;
}

#!/usr/bin/python
# -*- coding: utf8 -*-
"""
# Author: klchang
# Date: 2017.12.16
# Description: Compute the number of 1 in the binary representation of an integer.
"""

INT_BITS = 32 
MAX_INT = (1 << (INT_BITS - 1)) - 1  # Maximum Integer for INT_BITS


# Generic method: bitwise and operation with a number that has only one 1 in binary.
def number_of_1_in_binary_generic(num):
    
    count, bit = 0, 1
    while num and bit <= MAX_INT + 1:
        if bit & num:
            count += 1
            num -= bit
        bit = bit << 1

    return count
        

# Fast method: bitwise and operation between integer num and (num-1).
def number_of_1_in_binary_fast(num):
    count = 0
    while num:
        if num < - MAX_INT - 1 or num > MAX_INT:
            break
        print("iter %d: %d" % (count, num))
        count += 1
        num = num & (num-1)
        
    return count


def unitest():
    nums = [-5, 0, 5]
    # Generic Method
    print("-" * 30 + " Generic Method " + "-" * 30)
    for n in nums:
        print("The number of 1 in the binary representation of %d is %d.
" % (n, number_of_1_in_binary_generic(n)))
    # Fast Method
    print('
' + "-" * 30 + " Fast Method " + "-" * 30)
    for n in nums:
        print("The number of 1 in the binary representation of %d is %d.
" % (n, number_of_1_in_binary_fast(n)))

if __name__ == '__main__':
    unitest()

#pragma once

// The following macros define the minimum required platform.  The minimum required platform
// is the earliest version of Windows, Internet Explorer etc. that has the necessary features to run 
// your application.  The macros work by enabling all features available on platform versions up to and 
// including the version specified.

// Modify the following defines if you have to target a platform prior to the ones specified below.
// Refer to MSDN for the latest info on corresponding values for different platforms.
#ifndef _WIN32_WINNT            // Specifies that the minimum required platform is Windows Vista.
#define _WIN32_WINNT 0x0600     // Change this to the appropriate value to target other versions of Windows.
#endif

// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//

#pragma once

#include "targetver.h"

#include <stdio.h>
#include <tchar.h>



// TODO: reference additional headers your program requires here

// stdafx.cpp : source file that includes just the standard includes
// NumberOf1.pch will be the pre-compiled header
// stdafx.obj will contain the pre-compiled type information

#include "stdafx.h"

// TODO: reference any additional headers you need in STDAFX.H
// and not in this file

// NumberOf1.cpp : Defines the entry point for the console application.
//

// 《剑指Offer——名企面试官精讲典型编程题》代码
// 著作权所有者：何海涛

#include "stdafx.h"
#include <string.h>
#include <stdlib.h>

// ====================方法一====================
int NumberOf1(unsigned int n);

int NumberOf1Between1AndN_Solution1(unsigned int n)
{
    int number = 0;

    for(unsigned int i = 1; i <= n; ++ i)
        number += NumberOf1(i);

    return number;
}

int NumberOf1(unsigned int n)
{
    int number = 0;
    while(n)
    {
        if(n % 10 == 1)
            number ++;

        n = n / 10;
    }

    return number;
}

// ====================方法二====================
int NumberOf1(const char* strN);
int PowerBase10(unsigned int n);

int NumberOf1Between1AndN_Solution2(int n)
{
    if(n <= 0)
        return 0;

    char strN[50];
    sprintf(strN, "%d", n);

    return NumberOf1(strN);
}

int NumberOf1(const char* strN)
{
    if(!strN || *strN < '0' || *strN > '9' || *strN == '