이진 표현에서 1의 수를 센다.
가지고 놀기에 충분한 메모리가있는 경우 O (1)에있는 숫자의 이진 표현에서 1의 수를 계산하는 효율적인 방법입니다. 온라인 포럼에서 찾은 인터뷰 질문인데 답변이 없었습니다. 누군가가 뭔가를 제안 할 수 있습니까? O (1) 시간에 그것을 할 방법을 생각할 수 없습니까?
그것이 해밍 체중 문제, 일명 인구 수입니다. 링크는 효율적인 구현을 언급합니다. 인용 :
무제한 메모리를 사용하면 모든 64 비트 정수의 해밍 가중치에 대한 큰 조회 테이블을 간단히 만들 수 있습니다.
O(Number of 1's)시간에 비트를 계산하는 솔루션이 있습니다.
bitcount(n):
count = 0
while n > 0:
count = count + 1
n = n & (n-1)
return count
최악의 경우 (숫자가 2 ^ n-1이면 모든 1이 이진수로 표시됨) 모든 비트를 확인합니다.
편집 : 비트 카운트에 대한 아주 좋은 고정 시간 고정 메모리 알고리즘을 찾았습니다. 여기 C로 작성되었습니다.
int BitCount(unsigned int u)
{
unsigned int uCount;
uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}
여기에서 정확성에 대한 증거를 찾을 수 있습니다 .
n & (n-1)은 항상 최하위 1을 제거합니다.
따라서 다음과 같이 1의 수를 계산하는 코드를 작성할 수 있습니다.
count=0;
while(n!=0){
n = n&(n-1);
count++;
}
cout<<"Number of 1's in n is: "<<count;
프로그램의 복잡성은 다음과 같습니다. n에서 1의 수 (계속 <32).
다른 웹 사이트에서 다음 솔루션을 보았습니다.
int count_one(int x){
x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
return x;
}
public static void main(String[] args) {
int a = 3;
int orig = a;
int count = 0;
while(a>0)
{
a = a >> 1 << 1;
if(orig-a==1)
count++;
orig = a >> 1;
a = orig;
}
System.out.println("Number of 1s are: "+count);
}
countBits(x){
y=0;
while(x){
y += x & 1 ;
x = x >> 1 ;
}
}
그게 다야?
그것은 내 인생에서 가장 짧은 대답이 될 것입니다 : 조회 테이블.
분명히 조금 설명 할 필요가 있습니다. "만약 당신이 가지고 놀 수있는 충분한 메모리가 있다면"은 우리가 필요한 모든 메모리를 가지고 있다는 것을 의미합니다 (기술적 인 가능성은 신경 쓰지 마십시오). 이제 1 ~ 2 바이트 이상 조회 테이블을 저장할 필요가 없습니다. 기술적으로 Ω (로그 (N))이 아닌 O (1), 당신이 필요 번호를 읽을 수 있습니다하지만 그게 문제가 있다면 그렇다면, 대답은,이다, Ω (로그 (N))는 불가능 하다 - 어떤 더 짧습니다.
인터뷰에서 그들이 당신에게 기대하는 두 가지 대답 중 아무도 모릅니다.
또 다른 트릭이 있습니다. 엔지니어는 숫자를 가져 와서 n이 숫자 인 Ω (log (n))에 대해 이야기 할 수 있지만, 컴퓨터 과학자들은 실제로 우리가 입력 길이 의 함수로 실행 시간을 측정한다고 말할 것 입니다. 따라서 엔지니어가 Ω (log (n))이라고 부르는 것은 실제로 Ω (k)이며 여기서 k는 바이트 수입니다. 그래도 앞서 말했듯이 숫자를 읽는 것만으로도 Ω (k)이므로 그보다 더 잘할 수있는 방법은 없습니다.
아래에서도 작동합니다.
nofone(int x) {
a=0;
while(x!=0) {
x>>=1;
if(x & 1)
a++;
}
return a;
}
이 함수는 int이진 표현으로 1의 수를 가져와 반환합니다.
public static int findOnes(int number)
{
if(number < 2)
{
if(number == 1)
{
count ++;
}
else
{
return 0;
}
}
value = number % 2;
if(number != 1 && value == 1)
count ++;
number /= 2;
findOnes(number);
return count;
}
다음은 비트 연산자를 사용하는 C 솔루션입니다.
int numberOfOneBitsInInteger(int input) {
int numOneBits = 0;
int currNum = input;
while (currNum != 0) {
if ((currNum & 1) == 1) {
numOneBits++;
}
currNum = currNum >> 1;
}
return numOneBits;
}
다음은 2의 거듭 제곱을 사용하는 Java 솔루션입니다.
public static int numOnesInBinary(int n) {
if (n < 0) return -1;
int j = 0;
while ( n > Math.pow(2, j)) j++;
int result = 0;
for (int i=j; i >=0; i--){
if (n >= Math.pow(2, i)) {
n = (int) (n - Math.pow(2,i));
result++;
}
}
return result;
}
다음은이를 수행 할 수있는 두 가지 간단한 예제 (C ++)입니다.
__builtin_popcount ()를 사용하여 세트 비트 (1)를 간단히 계산할 수 있습니다.
int numOfOnes(int x) { return __builtin_popcount(x); }정수의 모든 비트를 반복하고 비트가 설정되었는지 확인한 다음 카운트 변수를 증가시킵니다.
int hammingDistance(int x) { int count = 0 for(int i = 0; i < 32; i++) if(x & (1 << i)) count++; return count; }
도움이 되었기를 바랍니다!
자바 스크립트에서 가장 좋은 방법은
function getBinaryValue(num){
return num.toString(2);
}
function checkOnces(binaryValue){
return binaryValue.toString().replace(/0/g, "").length;
}
여기서 binaryValue는 이진 문자열입니다. 예 : 1100
O (1)에서이 작업을 수행하기 위해 내가 생각할 수있는 유일한 방법은 ... 그것은 '속임수'와 물리적 장치를 사용하는 것입니다 (선형 또는 병렬 프로그래밍을 사용하면 한계가 O (log (k))라고 생각합니다) 여기서 k는 숫자의 바이트 수를 나타냅니다).
그러나 0/1 전압으로 각 비트를 출력 라인에 연결하는 물리적 장치를 매우 쉽게 상상할 수 있습니다. 그런 다음 O (1)의 '합산'라인에서 총 전압을 전자적으로 읽을 수 있습니다. 원하는 형식 (예 : 바이너리 인코딩 출력)으로 출력을 생성하기 위해 몇 가지 기본 회로 요소를 사용하여이 기본 아이디어를 더 우아하게 만드는 것은 매우 쉽지만, 본질적인 아이디어는 동일하며 전자 회로가 올바른 출력을 생성합니다. 고정 된 시간에 상태.
양자 컴퓨팅 가능성도 있다고 생각하지만 그렇게 할 수 있다면 간단한 전자 회로가 더 쉬운 해결책이라고 생각합니다.
저는 실제로 약간의 수작업을 사용하여이 작업을 수행했습니다. 16 개의 항목이있는 단일 조회 테이블이면 충분하며 이진 반복을 니블 (4 비트 튜플)로 나누기 만하면됩니다. 복잡성은 사실 O (1)이고 원하는 정수의 크기 (# 비트)에 특화된 C ++ 템플릿을 작성했습니다.
fwiw 당신은 (i & -i)가 당신에게 LS 1 비트를 반환하고 단순히 반복하여 정수가 0이 될 때까지 매번 lsbit를 제거한다는 사실을 사용할 수 있습니다.하지만 이것은 오래된 패리티 트릭입니다.
저는이 문제에 대한 아름다운 해결책을 알고 있다는 큰 믿음을 가지고 여기에 왔습니다. C 코드 :
short numberOfOnes(unsigned int d) {
short count = 0;
for (; (d != 0); d &= (d - 1))
++count;
return count;
}
그러나이 주제에 대해 약간의 연구를 마친 후 (다른 답변을 읽으십시오 :)) 5 가지 더 효율적인 알고리즘을 발견했습니다. 너무 사랑해!
이 작업을 위해 특별히 설계된 CPU 명령도 있습니다 popcnt. ( 이 답변에 언급 )
여기 에서 많은 알고리즘에 대한 설명 및 벤치마킹을 찾을 수 있습니다 .
아래 방법은 음수에서도 1의 수를 계산할 수 있습니다.
private static int countBits(int number) {
int result = 0;
while(number != 0) {
result += number & 1;
number = number >>> 1;
}
return result;
}
그러나 -1과 같은 숫자는 11111111111111111111111111111111로 이진수로 표시되므로 많은 이동이 필요합니다. 작은 음수에 대해 너무 많은 이동을 원하지 않는 경우 다른 방법은 다음과 같습니다.
private static int countBits(int number) {
boolean negFlag = false;
if(number < 0) {
negFlag = true;
number = ~number;
}
int result = 0;
while(number != 0) {
result += number & 1;
number = number >> 1;
}
return negFlag? (32-result): result;
}
파이썬이나 다른 어떤 것에서는 bin 문자열로 변환 한 다음 '0'으로 분할하여 0을 제거한 다음 결합하여 길이를 얻습니다.
len(''.join(str(bin(122011)).split('0')))-1
JS의 문자열 연산을 활용하면 다음과 같이 할 수 있습니다.
0b1111011.toString(2).split(/0|(?=.)/).length // returns 6
또는
0b1111011.toString(2).replace("0","").length // returns 6
나는 이것을 루비로 골프를 쳤고 결국
l=->x{x.to_s(2).count ?1}
사용법 :
l[2**32-1] # returns 32
분명히 효율적이지 않지만 트릭을 수행합니다. :)
Ruby 구현
def find_consecutive_1(n)
num = n.to_s(2)
arr = num.split("")
counter = 0
max = 0
arr.each do |x|
if x.to_i==1
counter +=1
else
max = counter if counter > max
counter = 0
end
max = counter if counter > max
end
max
end
puts find_consecutive_1(439)
두 가지 방법::
/* Method-1 */
int count1s(long num)
{
int tempCount = 0;
while(num)
{
tempCount += (num & 1); //inc, based on right most bit checked
num = num >> 1; //right shift bit by 1
}
return tempCount;
}
/* Method-2 */
int count1s_(int num)
{
int tempCount = 0;
std::string strNum = std::bitset< 16 >( num ).to_string(); // string conversion
cout << "strNum=" << strNum << endl;
for(int i=0; i<strNum.size(); i++)
{
if('1' == strNum[i])
{
tempCount++;
}
}
return tempCount;
}
/* Method-3 (algorithmically - boost string split could be used) */
1) split the binary string over '1'.
2) count = vector (containing splits) size - 1
Usage::
int count = 0;
count = count1s(0b00110011);
cout << "count(0b00110011) = " << count << endl; //4
count = count1s(0b01110110);
cout << "count(0b01110110) = " << count << endl; //5
count = count1s(0b00000000);
cout << "count(0b00000000) = " << count << endl; //0
count = count1s(0b11111111);
cout << "count(0b11111111) = " << count << endl; //8
count = count1s_(0b1100);
cout << "count(0b1100) = " << count << endl; //2
count = count1s_(0b11111111);
cout << "count(0b11111111) = " << count << endl; //8
count = count1s_(0b0);
cout << "count(0b0) = " << count << endl; //0
count = count1s_(0b1);
cout << "count(0b1) = " << count << endl; //1
참고URL : https://stackoverflow.com/questions/8871204/count-number-of-1s-in-binary-representation
'Programing' 카테고리의 다른 글
| C ++에서 세분화 오류 수정 (0) | 2020.11.01 |
|---|---|
| 유틸리티 클래스는 정적이어야합니까? (0) | 2020.11.01 |
| Python 읽기 전용 속성 (0) | 2020.11.01 |
| 스크립트를 실행할 수 없음 : 프로그램 실행을 계속하기에 메모리가 부족합니다. (0) | 2020.11.01 |
| Bootstrap 3-AJAX를 통해 모달 본문에 콘텐츠를로드하는 방법은 무엇입니까? (0) | 2020.11.01 |