비트에 대한 연산, 더 큰 값 얻기

Question

비트 연산에 익숙하지 않습니다. 나는이 시퀀스를 가지고있다 :

1 0 0 0 0 : 16 
--------------- 
0 1 1 1 1 : 15 
--------------- 
0 1 1 1 0 : 14 
--------------- 
. 
. 
. 
--------------- 
0 0 0 1 1 : 3 
--------------- 
0 0 0 1 0 : 2 
--------------- 
0 0 0 0 1 : 1 
--------------- 

"1"이 여러 개 있는지 먼저 확인하고 싶다. 이 경우 더 큰 십진수 값을 가진 것을 제거하고 끝내고 더 큰 것을 남기고 싶습니다. 예를 들어 15, 4 "1", 큰 "1"8 ","0 0 1 1 1 : 7 "더 큰"1 ""4 "있습니다. 어떻게해야합니까?

Answer 1

에게 있습니다 : 나는 당신을 가정

unsigned chk_bits(unsigned int x) { 
    unsigned i; 
    if (x != 0 && (x & (x-1)) != 0) { 
     /* More than one '1' bit */ 
     for (i = ~(~0U >> 1); (x & i) == 0; i >>= 1) 
      ; /* Intentionally left blank */ 
     return x & ~i; 
    } 
    return x; 
} 

참고 부호없는 숫자를 처리하고 있습니다. 부호 확장으로 인해 오른쪽 시프트가 부호있는 정수에 정의 된 구현이기 때문에 일반적으로 더 안전합니다.

if 문은 x에 두 개 이상의 비트가 설정되어 있는지 확인합니다. x가 x & (x-1)이 101100000입니다 다음, 101100100 경우 x & (x-1)는 첫 번째 '1'최하위 비트와 x (예를 들어 해제와 같은 숫자를 얻을 수있는 알려진 방법입니다 따라서, if는 말한다.

x가 0이 아니고 첫 번째 비트를 1로 설정하면 (LSB에서 MSB로) 0이 아닌 값이 반환되고 ...

이는 x에 1 비트 이상 설정되었다는 것과 동일합니다. 설정되어있는 최초의 최상위 비트에서 정지 x의 모든 비트를 통해

다음, 우리 루프. i는 1000000000000000000000000000으로 초기화되며, x & i 우리가 1 첫 번째 최상위 비트를 발견하는 시점에서 0이 아닌 무언가로 평가 될 때까지 루프 바로 이동 유지합니다. 이 시점에서 i의 보수를 취하면 ~i은 모든 비트가 1 인 유일한 비트 (x의 최상위 비트에 해당)를 제외하고 모든 비트가 1로 설정된 숫자이므로 x에서이 비트를 끄는 마스크가 생성됩니다.). 따라서 ANDing with x은 원하는 것을 제공합니다. 이 특정 표현을 가정하지 않으며, unsigned 32 또는 64 비트는 사실에 의존 않습니다

코드는 휴대용이다.

업데이트 : 귀하의 의견을 읽은 후 자세한 설명을 추가하겠습니다.

1 단계 - 이해 x & (x-1)는 무엇을 :

우리는 여기에 두 가지 가능성을 고려해야합니다 :

• x
  은 1 (.......0011001)
• x로 끝나는 0 (.......0011000)
로 끝 첫 번째 경우

는, 그 012,372를 참조하기 쉽다 72,246,154,134,단지 x 예 0011001 - 1 = 0011000 들어 0으로 설정 가장 오른쪽 비트이기 때문에, 효과적으로 x & (x-1)은 x-1 것이다. ,

번째 경우, 이해하기 다소 어려울 수도 있지만 x의 우측 비트가 0이면 모든 0 비트는 최하위 비트에서 시작하여 1 비트의 전환과 다음 x-1는 x 것 왜이

1101011000 - 1 = 11101010111

입니다 : 1이 발견 될 때까지 내가 당신에게 예를 들게는이 새로운 사람을 까다로운 일이 될 수 있기 때문에, 어떤은 0

으로 켜져 있습니까? 왜냐하면 0으로 끝나는 이진수의 이전 수는 가장 오른쪽 위치에 하나 이상의 1 비트가 채워진 이진수이기 때문입니다. 우리가 그것을 증가시킬 때, 10101111101111 + 1처럼, 우리는 다음 "자유"위치, 즉 다음 0 위치를 증가시켜 그것을 1로 바꾸고 그 위치의 오른쪽에있는 모든 1- 비트를 0입니다. 이것은 base-n 계산이 작동하는 방식입니다. 유일한 차이점은 base-2의 경우 0과 1 만 가질 수 있다는 것입니다.

기본 -10 계산 방식에 대해 생각하십시오. 숫자가 다 떨어지면 값이 랩되고 왼쪽에 새 숫자가 추가됩니다. 999 뒤에 오는 것은 무엇입니까? 다시 계산이 다시 시작되고 왼쪽에 새 숫자가 표시되고 9가 0으로 바뀝니다. 결과는 1000입니다. 이진 산술에서도 같은 일이 발생합니다.

2 진수로 계산하는 과정을 생각해보십시오. 우리는 단지 2 비트, 0과 1이 있습니다

• 0 (십진수 0) 1
• 1 (소수점 - 지금, 우리는 비트에서 실행 한 다음 번호의 경우,이 1이 0으로 설정됩니다. , 그리고 우리는 왼쪽에 새로운 비트를 추가해야합니다.)
• 10 (십진수 2)
• 11 (10 진수 3 - 프로세스가 다시 반복 될 예정입니다. 따라서 비트가 부족하여 이제 2 비트가됩니다. 0으로 바뀌고 왼쪽에 새로운 비트가 추가되어야 함)
• 100 (소수 4)
101 (소수 5)
• 110
• 111
• ...

난 바와 같이 패턴이 정확히 어떻게 참조 (동일한 절차를 다시 반복)?

x-1 지금 x의 1 개의를 x와 x-1, 오른쪽 공의를하는 비교 및 ​​x에서 가장 오른쪽 1 x-1 지금 0 동안 x가 0으로 끝나는 우리가, 제 2 케이스를 고려하고있다 기억하십시오. 따라서, 동일하게 유지 x의 일부만 따라서 0

으로 전환 된 (1)의 좌측에, x & (x-1) 첫번째 우측 1 비트가 있었던 위치까지 x와 동일 할 것이라는 것이다. 이제 우리는 두 경우 모두 x & (x-1)이 사실상 x의 오른쪽 1 비트를 삭제한다는 것을 알 수 있습니다.

두 번째 단계 : 정확히 ~0U >> 1은 무엇입니까?

문자 U은 unsigned을 나타냅니다. C에서 정수 상수는 사용자가 지정하지 않으면 int입니다. 정수 상수에 U을 추가하면 부호가 없습니다. 앞에서 언급했듯이 오른쪽 시프 팅이 부호 확장을 수행하는지 여부가 정의되어 있기 때문에 이것을 사용했습니다. 단항 연산자 ~은 보수 연산자이며, 숫자를 가져와 그 보수를 취합니다. 0 비트가 1로 바뀌고 1 비트가 0으로 바뀝니다. 따라서 ~ 0은 1로 채워지는 숫자입니다. 11111111111.... 그런 다음 바로 한 위치로 이동하므로 이제는 01111111....이고이 표현은 ~0U >> 1입니다. 마지막으로, 나는 그 보충 코드를 받아 100000....을 얻습니다. 코드는 ~(~0U >> 1)입니다. 이것은 가장 왼쪽 비트가 1로 설정되고 다른 모든 비트가 0으로 설정된 숫자를 가져 오는 휴대용 방식 일뿐입니다.

K & R 제 2 장,보다 자세하게는 2.9 절에서 살펴볼 수 있습니다. 48 페이지부터 비트 연산자가 제공됩니다. 운동 2-9는 왜 독자가 x & (x-1)가 작동 하는지를 설명하게합니다. 혹시 알고 계시지 않을 경우, K & R은 C의 제작자 인 Kernighan and Ritchie가 쓴 C 프로그래밍 언어를 설명하는 책입니다. 책 제목은 "The C Programming Language"입니다. 두번째 버전. 모든 훌륭한 C 프로그래머는이 책에서 C를 배웠다.

Answer 2

"1"이 둘 이상 있는지 먼저 확인하고 싶습니다.

다수의 이진 표현에서 하나 1

있는 경우는 그 형태 2 X로 표현 될 수있는 수이다. 예 :

 
4  00000100 2^2 
32 00010000 2^5 

따라서 하나만 확인하려면이 속성을 확인하면됩니다. 로그 (X이) 정수 인 경우는 바이너리 표현의에

은 다음 단일 1있다. (X가)/_{로그 Y 넌 calculate 로그 2 (X)}

로그 ₂ (X) =가 _{를 기록 할 수}

Y (2)

여기서, y은 표준 로그 함수로는 10 또는 e입니다. 여기

다음은 원하는 것을 그 코드의 솔루션

double logBase2 = log(num)/log(2); 
if (logBase2 != (int)logBase2) { 

    int i = 7; 
    for (;i >0 ; i--) { 

     if (num & (1 << i)) { 

      num &= ~(1 << i); 
      break; 
     } 
    } 
}