C에서 회전 교대를 수행하는 방법

Question

다음과 같은 질문이 있습니다. 포함 된 어셈블리없이 C에서 회전 교대를 수행하는 방법. 더 구체적으로, 어떻게 시프트 회전 32 비트 int.

이제이 문제를 long long int 유형의 도움으로 해결할 예정입니다.하지만 좀 더보기 싫어서 더 우아한 방법이 있는지 알고 싶습니다.

친절하게 제공합니다.

Answer 1

(향후 독자들에게 경고) : 위키 백과의 코드는 비정상 asm (gcc에 분기 또는 cmov 포함)을 생성합니다. 효율적인 UB 프리 회전을 위해서는 Best practices for circular shift (rotate) operations in C++을 참조하십시오. Wikipedia에서

---

:

unsigned int _rotl(unsigned int value, int shift) { 
    if ((shift &= 31) == 0) 
     return value; 
    return (value << shift) | (value >> (32 - shift)); 
} 

unsigned int _rotr(unsigned int value, int shift) { 
    if ((shift &= 31) == 0) 
     return value; 
    return (value >> shift) | (value << (32 - shift)); 
} 

Answer 2

이 대답은 내가 Best-practices for compiler-friendly rotates에 게시 무엇의 중복입니다.

자세한 내용은 my answer on another question을 참조하십시오. 당신이 할 수 있도록, 임의의 정수 유형에 대한

uint32_t rotl32 (uint32_t x, unsigned int n) 
{ 
    const unsigned int mask = (CHAR_BIT*sizeof(x)-1); 

    assert ((n<=mask) &&"rotate by type width or more"); 
    n &= mask; // avoid undef behaviour with NDEBUG. 0 overhead for most types/compilers 
    return (x<<n) | (x>>((-n)&mask)); 
} 

작품뿐만 아니라 uint32_t :

어떤 정의되지 않은 동작을 방지 C의 회전을 표현하는 가장 컴파일러 친화적 인 방법은 John Regehr의 구현 것 같다 여러 버전. 이 버전 inlines to a single rol %cl, reg (또는 rol $imm8, reg)은 컴파일러가 명령에 이미 마스크 작업이 내장되어 있음을 알고 있기 때문에 x86에 있습니다.

임시적으로 int에 저장된 16 비트 값을 가지고있을 때 실수로 잘못된 너비의 회전을하고 싶지 않기 때문에 피연산자 유형에 템플릿을 지정하지 않는 것이 좋습니다. 특히 정수 승격 규칙은 부호가없는 유형이 포함 된 표현식의 결과를 int으로 바꿀 수 있기 때문에 특히 그렇습니다.

x에 부호없는 유형을 사용하고 반환 값이 맞는지 확인하십시오. 그렇지 않으면 회전되지 않습니다. (gcc는 0보다 오히려 부호 비트의 복사본을 이동 시키므로, 두 개의 쉬프트 된 값이 합쳐져서 OR 일 때 문제가 발생합니다.)

Answer 3

쓰레드가 오래되었지만, 나는 두 센트를 토론하고 문제의 해결책을 제안하십시오. 그것이 가치가 있기를 바라지 만, 내가 틀렸다면 제발 저를 교정하십시오.

나는 효율적이고 안전한 회전 방법을 찾고있을 때 실제로 그 해결책이 없다는 것에 놀랐습니다. 여기 몇 가지 관련 스레드를 발견 https://blog.regehr.org/archives/1063 (안전, 효율적인, 그리고 C/C++에서 휴대용 회전) (분기하지만 안전 포함) Best practices for circular shift (rotate) operations in C++ 및 위키 피 디아 스타일 :

uint32_t wikipedia_rotl(uint32_t value, int shift) { 
    if ((shift &= 31) == 0) 
     return value; 
    return (value << shift) | (value >> (32 - shift)); 
} 

묵상 조금 후 결과적으로 알리미가 분기없이 항상 < 시프트 조건에 맞는 약수보다 항상 낮기 때문에 모듈로 나누기가 기준에 맞을 것으로 나타났습니다.도면의 수학적 관점에서 :

∀ x> = 0, Y (X 개조 Y) < Y 우리의 경우 매에서

정확히이다 (X의 32 %) < 32 우리 성취하고 싶다. (그리고 그래, 내가 경험적 것을 확인하고 항상 < 32)

#include <stdint.h> 
uint32_t rotl32b_i1m (uint32_t x, uint32_t shift) 
    { 
    shift %= 32; 
    return (x<<n) | (x>>(32-shift)); 
    } 

또한 모드()의 100 개 비트를 가정 해 봅시다의 실제 회전이 3 번 전체 32 개 비트를 회전하고 있기 때문에, 과정을하는 본질적으로 단순화 아무것도 변경하지 않고 4 비트를 변경합니다. 그래서 100 % 32 == 4를 계산하고 4 비트를 회전하는 것이 더 나은가요? 그것은 어쨌든 단일 프로세서 연산을 필요로하고 상수 값 + 하나의 명령을 더해서 인자를 스택에서 가져와야합니다. 그러나 위키피디아처럼 if()를 사용하여 분기하는 것보다 여전히 좋습니다.

그럼, 어떻게 생각하니?