C에서 짝수의 비트 반전

Question

소녀는 보드에 홀수와 짝수로 N 개의 숫자를 쓴 다음 짝수를 수정하고 이진 표현을 왼쪽에서 오른쪽으로 반전하고 각각을 우수. 같은 코드를 작성하십시오.

  int a[100000]; 
      while (t != 0) // t is the number in which input is taken 
      { 
       k = t & 1; 
       if (k == 1)    
       a[i] = 0; // a is the array in which bits of new number will be stored 
       else 
       a[i] = 1; 
       i++; 
       t = t >> 1; 
      } 
      for (j = i; j >= 0; j--) 
      { 
       if (a[j] == 1) 
       { 
        num = num + pow(2,j)*a[j]; // num is the number to be formed 
       } 
      } 
       cout<<num<<"\n"; 

하지만 내 대답은 8 예를 들어, 일부 값에 대한 잘못된 나옵니다, 그것은 7 출력 :

0 <= n <= 10^7 

나는 내 일부 코드는 다음과 같습니다 곳,에 대한 코드를했다. 이게 뭐가 잘못 되었 니? 감사!

해결 링크 :

http://www.spoj.com/problems/EC_CONB/

편집 :

  while (t != 0) 
      { 
       k = t & 1; 
       if (k == 1)    
       a[i] = 0; 
       else 
       { 
        a[i] = 1; 
        num = num + pow(2,i); 
       } 
       i++; 
       t = t >> 1; 
      } 
      cout<<num<<"\n"; 
     } 

이 여전히 동일한 문제를 도시 7.

Answer 1

이 문제는 실제로 반전되지 않는 비트를 반전 시키길 원합니다. 따라서 if k == 1을 점검하고 대신 0을 넣는 부분은 비트를 반전시키기 때문에 올바르지 않습니다.

이

while (t != 0) 
{ 
    k = t & 1; 
    // push the output array to the left 
    num <<= 1; 
    // add the read bit to the beginning of the output array 
    num += k; 
    t = t >> 1; 
} 

설명 :

이

기본적인 아이디어는

1000 (8) -> 0001 (1) 
1010 (10) -> 0101 (5) 

샘플 코드 코드를 기반으로 : 당신이해야 할 일은

는 다음과 같이 비트의 순서를 역입니다 입력 번호에서 비트를 하나씩 읽은 다음 출력 번호의 시작 부분으로 푸시합니다. 다음은

각 반복에서 번호 (1011) 반전의 흔적입니다 :

iterations 0  1  2  3 4 
input   1011 101 10 1 0 
output  0  1  11 110 1101 

Answer 2

등 (8)의 값을 출력한다 (피트, 응답에 응답하여)

i을 증가시킨 후 a[i]을 읽는 것으로 보이므로 동작은 정의되지 않습니다.

배열을 만드는 대신 결과를 첫 번째 루프에 축적하십시오.

Answer 3

어레이? 루프? 필요 없습니다.

같은 숫자가 완전히 같이, 마우스 오른쪽 정당화 다음 정수 반전과 동등 역전

// reverse from http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel 
// swap odd and even bits 
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1); 
// swap consecutive pairs 
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2); 
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4); 
// swap bytes 
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8); 
// swap 2-byte long pairs 
v = (v >> 16   ) | (v    << 16); 
// right-justify 
v /= v & -v; 

v가 uint32_t되어야 (시험되지 않음).