剣指offerバイナリ中1の個数Python and C++
1494 ワード
タイトルの説明
整数を入力し、その数のバイナリ表現の1つの数を出力します.ここで負数は符号で表す
構想
整数が0に等しくない場合、整数のバイナリ表現の少なくとも1ビットは1である.
まず、この数の右端が1であると仮定すると、その数から1を減算すると、右端が0になり、他のビットは変わらない.
最後のビットが1ではなく0であり、最も右の1がm位であると仮定すると、この数から1を減算すると、m位が0になり、m右のビットが1になり、m以前のビットは変わらない.
上の2つのケースをまとめると、1つの整数から1を減算すると、右端の1を0にし、後ろに0があれば0を1にします.では、1つの整数から1を減算し、その整数とビット演算を行い、右端の1を0にすることに相当します.例えば、1100と1011をビットと演算して、1000を得ます.では、1つの整数の中に1が何個あるかで、このような演算を何回することができます.
問題の起こり得る問題を解く
ここで最大の問題は,単純な実装コードではエラーが発生し,pythonではまずバイナリにビット数がないという概念を明確にしているので,負数の真の表現方法を得ることができないことである.
得られた最終結果pythonは正数とみなされ(ビット数の概念がないため、トップの1はシンボルビットを代表しない)、得られる
ただ形式的には-3の補符号と同じです.pythonでは,負数に対して右シフト操作でもn&(n−1)操作でもデッドサイクルに陥る.そこで,上記の小さなテクニックを用いて,負数の影響を0 xffffff相とpythonが考える正数(機械における補符号と同じ)に変換するために用いた.そして正数で操作すれば簡単です
python
C++
整数を入力し、その数のバイナリ表現の1つの数を出力します.ここで負数は符号で表す
構想
整数が0に等しくない場合、整数のバイナリ表現の少なくとも1ビットは1である.
まず、この数の右端が1であると仮定すると、その数から1を減算すると、右端が0になり、他のビットは変わらない.
最後のビットが1ではなく0であり、最も右の1がm位であると仮定すると、この数から1を減算すると、m位が0になり、m右のビットが1になり、m以前のビットは変わらない.
上の2つのケースをまとめると、1つの整数から1を減算すると、右端の1を0にし、後ろに0があれば0を1にします.では、1つの整数から1を減算し、その整数とビット演算を行い、右端の1を0にすることに相当します.例えば、1100と1011をビットと演算して、1000を得ます.では、1つの整数の中に1が何個あるかで、このような演算を何回することができます.
問題の起こり得る問題を解く
ここで最大の問題は,単純な実装コードではエラーが発生し,pythonではまずバイナリにビット数がないという概念を明確にしているので,負数の真の表現方法を得ることができないことである.
n = -3
n = n & 0xffffffff #n=4294967293
bin(n)# :'0b11111111111111111111111111111101'
得られた最終結果pythonは正数とみなされ(ビット数の概念がないため、トップの1はシンボルビットを代表しない)、得られる
0b11111111111111111111111111111101
ただ形式的には-3の補符号と同じです.pythonでは,負数に対して右シフト操作でもn&(n−1)操作でもデッドサイクルに陥る.そこで,上記の小さなテクニックを用いて,負数の影響を0 xffffff相とpythonが考える正数(機械における補符号と同じ)に変換するために用いた.そして正数で操作すれば簡単です
python
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
count = 0
if n < 0:
n = n & 0xffffffff
while n:
n = n & (n-1)
count = count+1
return count
C++
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while (n != 0) {
n = (n - 1) & n;
++count;
}
return count;
}
};