C 비트 필드 회전 (설명 필요)

Question

바이트를 1 비트 왼쪽으로 회전하고 싶습니다. 이 사이트에서 몇 가지 예를보고이 코드를 보았습니다. 그것이 작동하더라도, 나는 에 단계별로 어떤 단계를 부탁드립니다 어떻게 작동합니까.

unsigned int _rotl(const unsigned int value, int shift) 
{ 
    if ((shift &= sizeof(value)*8 - 1) == 0)   //What does this do? 
     return value; 
    return (value << shift) | (value >> (sizeof(value)*8 - shift)); 
} 

우선 첫 번째 부분은 무엇을합니까? 그리고 마지막 부분은 그만큼 변하지 않으므로 비트의 일부를 지울 것입니다. 예를 들어

:

말

value= 0x50 //01010000 
shift = 4 

내가

value << shift 

01010000 << 4 => 00000000 

및 >> 값 을해야합니다 (sizeof 연산자 (값) * 8 - 시프트)

01010000>> (4*8 - 4) => 00000000 

둘 다 OR 연산을하면 0이됩니다. 내 이해는 분명히 잘못되었지만 다른 사람이 나 같은 초심자를 '무시할 것'이라고 생각합니다. 감사.

Answer 1

은의가 단계적으로 보자

unsigned int _rotl(const unsigned int value, int shift) 
{ 
    if ((shift &= sizeof(value)*8 - 1) == 0)   //What does this do? 
    return value; 
    return (value << shift) | (value >> (sizeof(value)*8 - shift)); 
} 

첫 번째 줄 :

if ((shift &= sizeof(value)*8 - 1) == 0)   //What does this do? 

이 문을 최적화이고 체크 한 줄에 출시했다. 두 가지 조건 중 하나가 충족되는 경우 TRUE를 반환 :

1. 시프트 제로 shift에 의해 지정된 회전 수는 영향

이없는 것

(모든 비트를 회전하지 않는 즉) 그 문은 그렇지 않으면 FALSE를 반환하지만 원하는 결과를 얻는 데 필요한 최소 회전 수를 계산하고 그 값을 shift에 저장합니다. 즉, shift = shift % size_of_integer_data_type을 계산합니다.

예를 들어, 32 비트 정수가있는 경우 32 비트로 회전하면 아무 것도 수행되지 않습니다. 64, 96 또는 32의 다른 배수로 회전하면 아무 것도 수행하지 않습니다. 우리의 로테이션 효과가 아무런 효과가 없다면 우리는 많은 시간을 절약하고 일찍 종료해야합니다.

그러나 우리는 필요한 것보다 훨씬 많은 작업을 지정할 수도 있습니다. 32 비트 정수이면 1 비트 씩 회전하면 33 비트 또는 65 비트 또는 97 비트 등으로 회전하는 것과 같은 효과가 있습니다.이 코드는이 사실을 인식하므로 shift를 97로 지정하면 , shift=1을 재 할당하고 불필요한 회전을 제거합니다.

문 sizeof(value)*8 - 1은 value의 표현에있는 비트 수보다 1을 리턴합니다. 예를 들어, sizeof(value)이 4 (32 비트 정수가있는 시스템에서)로 평가되는 경우 4*8 - 1 = 31입니다.

&= 연산자는 비트 AND이며 할당되어 있습니다. 즉, shift과 sizeof(value)*8 - 1 사이의 비트 AND를 수행하고 그 결과를 shift에 할당한다는 의미입니다. 앞에서와 같이 표현식의 오른쪽은 value의 비트 수를 뺀 것과 같습니다. 따라서, shift의 비트를 value의 표현의 크기보다 크게 마스크하는 효과가 있으며, 차례로 shift = shift % size_of_integer_data_type을 계산하는 효과가 있습니다.

구체적으로 32 비트 케이스를 다시 생각해보십시오. 이전과 마찬가지로 sizeof(value)*8-1은 31로 평가됩니다. 비트 단위로이 값은 0000 0000 0000 0000 0000 0000 0001 1111입니다. 이 값은 shift과 비트 단위 AND 연산됩니다. shift의 6 ~ 32 번째 위치의 비트는 0으로 설정되고, 1 ~ 5 번째 위치의 비트는 변경되지 않습니다. 97 회전을 지정하면 결과는 1입니다.

0000 0000 0000 0000 0000 0000 0110 0001 (97) 
& 0000 0000 0000 0000 0000 0000 0001 1111 (31) 
========================================= 
    0000 0000 0000 0000 0000 0000 0000 0001 (1) 

여기에서 할 수있는 마지막 일은 C에서, 할당 문의 반환 값은 할당 된 값입니다, 그것을 기억하는 것입니다. 따라서 새 값 shift이 0이면 즉시 반환하고, 그렇지 않으면 우리는 계속 진행합니다.

번째 라인 :

return (value << shift) | (value >> (sizeof(value)*8 - shift)); 

C가 (단지 좌우 시프트있다) 우리는 별도로 하위 비트 및 상위 비트를 계산해야하는 회전 조작이 없으므로 및 그런 다음 비트 OR로 결합하십시오. 이 선은 각면을 별도로 계산하는 간단한 문제입니다.

문장 value << shift은 상위 비트를 계산합니다. 비트 패턴을 shift 자리만큼 왼쪽으로 이동합니다. 다른 명령문은 비트 패턴을 오른쪽으로 size_of_integer_type - shift 비트 씩 이동하여 하위 비트를 계산합니다. 예제에서 쉽게 볼 수 있습니다.

value가 소수 값 65535를 가지고 있다고 가정하고 shift는 그 값 (26)을 가지고 시작 값은 다음

는

1111 1100 0000 0000 0000 0000 0000 0000 (65535 << 26) 

우측 시프트 준다 :

0000 0000 0000 0000 1111 1111 1111 1111 (65535) 

좌측 시프트 우릴 준다 우리 :

0000 0000 0000 0000 0000 0011 1111 1111 (65535 >> 6) 

그러면 bitwise-OR com 당신은이 코드를 다시 작성하고 같은 올바른 결과를 얻을 수

1111 1100 0000 0000 0000 0000 0000 0000 (65535 << 26) 
| 0000 0000 0000 0000 0000 0011 1111 1111 (65535 >> 6) 
========================================= 
    1111 1100 0000 0000 0000 0011 1111 1111 (65535 rot 26) 

: 이러한 결과를 바인

질문의 값은 아마도 32 비트 숫자입니다 (

unsigned int _rotl(const unsigned int value, int shift) 
{ 
    //Assume 8 bits in a byte 
    unsigned bits_in_integer_type = sizeof(value)*8; 
    shift = shift % bits_in_integer_type; 

    if(shift == 0) return value; //rotation does nothing 

    unsigned high_bits = value << shift; 
    unsigned low_bits = value >> (bits_in_integer_type - shift); 

    return high_bits | low_bits; 
} 

Answer 2

unsigned int _rotl(const unsigned int value, int shift) 
{ 
    // If all bits in value are zero, do nothing and return 
    int bitmaskOfAllOnes = sizeof(value)*8 - 1; 
    if ((shift &= bitmaskOfAllOnes) == 0)   //What does this do? 
     return value; 

    // Shift value to the left 
    (value << shift) 
    // shifting right to handle the wrap around 
    | (value >> (sizeof(value)*8 - shift)); 
} 

e.g. using 16-bit ints 
value = 0x1001 
shift = 4 
sizeof(value) => 2 
//sizeof(value)*8 - 1 => 0xffff 
sizeof(value)*8 - 1 => 15 Decimal 
shift &= bitmaskOfAllOnes => 0x1001 (i.e. not zero) 
value << shift => 0x0010 
sizeof(value)*8 - shift => 12 
value >> (sizeof(value)*8 - shift) => 0x001 
0x0010 | 0x001 => 0x0011