C ++의 순환 이동 (회전) 작업에 대한 모범 사례
왼쪽 및 오른쪽 시프트 연산자 (<< 및 >>)는 이미 C ++에서 사용할 수 있습니다. 그러나 원형 이동이나 회전 작업을 수행하는 방법을 알 수 없었습니다.
"왼쪽으로 회전"및 "오른쪽으로 회전"과 같은 작업을 어떻게 수행 할 수 있습니까?
여기에서 오른쪽으로 두 번 회전
Initial --> 1000 0011 0100 0010
결과는 다음과 같습니다.
Final --> 1010 0000 1101 0000
예가 도움이 될 것입니다.
(편집자 주 : C에서 회전을 표현하는 많은 일반적인 방법은 회전 수가 0 인 경우 정의되지 않은 동작이 발생하거나 단일 회전 기계 명령어 이상으로 컴파일됩니다.이 질문에 대한 답변은 모범 사례를 문서화해야합니다.)
asm gcc / clang이 x86에 대해 생성하는 것에 대한 자세한 내용은 다른 회전 질문에 대한이 답변 의 이전 버전을 참조하십시오 .
Undefined Behavior를 피하는 C 및 C ++에서 회전을 표현하는 가장 컴파일러 친화적 인 방법은 John Regehr의 구현 인 것 같습니다 . 유형의 너비에 따라 회전하도록 조정했습니다 (와 같은 고정 너비 유형 사용 uint32_t).
#include <stdint.h> // for uint32_t
#include <limits.h> // for CHAR_BIT
// #define NDEBUG
#include <assert.h>
static inline uint32_t rotl32 (uint32_t n, unsigned int c)
{
const unsigned int mask = (CHAR_BIT*sizeof(n) - 1); // assumes width is a power of 2.
// assert ( (c<=mask) &&"rotate by type width or more");
c &= mask;
return (n<<c) | (n>>( (-c)&mask ));
}
static inline uint32_t rotr32 (uint32_t n, unsigned int c)
{
const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);
// assert ( (c<=mask) &&"rotate by type width or more");
c &= mask;
return (n>>c) | (n<<( (-c)&mask ));
}
뿐만 아니라 부호없는 정수 유형에서 작동 uint32_t하므로 다른 크기의 버전을 만들 수 있습니다.
static_assert예를 들어 일부 24 비트 DSP 또는 36 비트 메인 프레임에서는 그렇지 않은 많은 안전 검사 ( 유형 너비가 2의 거듭 제곱 인 경우 포함)가 포함 된 C ++ 11 템플릿 버전도 참조하세요 .
회전 너비를 명시 적으로 포함하는 이름을 가진 래퍼의 백엔드로만 템플릿을 사용하는 것이 좋습니다. 정수 승격 규칙은 rotl_template(u16 & 0x11UL, 7)16 비트가 아닌 32 비트 또는 64 비트 회전을 수행함을 의미합니다 (의 너비에 따라 다름 unsigned long). 심지어 uint16_t & uint16_t로 승격 signed int플랫폼에서 제외하고, C ++의 정수 프로모션 규칙에 의해 int보다 넓은입니다 uint16_t.
x86 에서이 버전 은 x86 회전 및 시프트 명령어 가 C 소스와 동일한 방식으로 시프트 카운트를 마스크 한다는 것을 컴파일러가 알고 있기 때문에 컴파일하는 컴파일러가 있는 단일rol r32, cl (또는 rol r32, imm8)에 인라인됩니다 .
x86에서이 UB 회피 관용구에 대한 컴파일러 지원 uint32_t x및 unsigned int n가변 카운트 시프트 :
- clang : clang3.5 이후 가변 횟수 회전, 그 전에 여러 시프트 + 또는 insns로 인식됩니다.
- gcc : gcc4.9 이후 가변 카운트 회전 , 그 전에 여러 시프트 + 또는 insns로 인식됩니다. gcc5 이상은 위키피디아 버전에서도 변수 개수에 대해
ror또는rol명령어를 사용하여 분기와 마스크를 최적화 합니다. - icc : ICC13 또는 이전 버전부터 가변 카운트 회전에 지원됩니다 . 상수 카운트
shld edi,edi,7는rol edi,7BMI2를rorx eax,edi,25MOV 저장에 사용할 수없는 경우 일부 CPU (특히 AMD, 일부 Intel) 보다 느리고 더 많은 바이트를 사용 하는 회전 사용 입니다 . - MSVC : x86-64 CL19 : 고정 카운트 회전에 대해서만 인식됩니다. (wikipedia 관용구는 인식되지만 분기 및 AND는 최적화되지 않습니다.) x86 (x86-64 포함) 에서
_rotl/_rotr내장 함수를 사용합니다<intrin.h>.
ARM 용 GCC 사용은 and r1, r1, #31가변 수의 회전에 대한 있지만, 여전히 단일 명령과 실제 회전을한다 : ror r0, r0, r1. 따라서 gcc는 회전 횟수가 본질적으로 모듈 식이라는 것을 인식하지 못합니다. ARM 문서에서 "시프트 길이가있는 ROR n,, 32 이상은 시프트 길이가있는 ROR과 동일합니다 n-32"라고 말합니다 . ARM에서 왼쪽 / 오른쪽 시프트가 카운트를 포화시키기 때문에 gcc가 혼란스러워서 32 이상 시프트하면 레지스터가 지워집니다. (x86과 달리, 시프트는 회전과 동일하게 카운트를 마스킹합니다). 회전 관용구를 인식하기 전에 AND 명령이 필요하다고 결정했을 것입니다. 해당 대상에서 비 원형 시프트가 작동하는 방식 때문입니다.
현재 x86 컴파일러는 여전히 추가 명령어를 사용하여 8 비트 및 16 비트 회전에 대한 변수 수를 마스킹합니다. 아마도 ARM에서 AND를 피하지 않는 이유와 같습니다. 성능이 x86-64 CPU의 회전 수에 의존하지 않기 때문에 이것은 놓친 최적화입니다. (카운트 마스킹은 성능상의 이유로 286으로 도입되었습니다. 현대 CPU와 같은 일정한 지연 시간이 아니라 반복적으로 시프트를 처리했기 때문입니다.)
BTW는 가변 카운트 회전에 대해 오른쪽 회전을 선호하므로 컴파일러가 32-n오른쪽 회전 만 제공하는 ARM 및 MIPS와 같은 아키텍처에서 왼쪽 회전을 구현 하지 않도록합니다 . (이는 컴파일 시간 상수로 최적화됩니다.)
재미있는 사실 : ARM 정말 전용 이동 / 회전 명령이없는, 그것은 그냥 MOV의 소스 피연산자 ROR 모드에서 배럴 쉬프터를 거치지가 : mov r0, r0, ror r1. 따라서 회전은 EOR 명령 또는 기타에 대한 레지스터 소스 피연산자로 접을 수 있습니다.
n및 반환 값에 대해 서명되지 않은 유형을 사용하는지 확인하십시오. 그렇지 않으면 rotate가되지 않습니다 . (x86 타겟에 대한 gcc는 산술 오른쪽 시프트를 수행하여 0이 아닌 부호 비트 사본에서 OR시프트하므로 두 값을 함께 시프트 할 때 문제가 발생합니다 . 부호있는 음수 정수의 오른쪽 시프트는 C에서 구현 정의 동작입니다.)
또한 부호(-n)&31 있는 유형은 1의 보수 또는 부호 / 크기가 될 수 있고 부호없는 또는 2의 보수로 얻는 모듈 식 2 ^ n과 동일하지 않기 때문에 시프트 카운트가 부호없는 유형인지 확인하십시오 . (Regehr의 블로그 게시물에 대한 의견 참조). unsigned int내가 본 모든 컴파일러에서 x. 일부 다른 유형은 실제로 일부 컴파일러의 관용구 인식을 무력화하므로 동일한 유형을 x.
일부 컴파일러는 회전에 대한 내장 함수를 제공 하는데, 이식 가능한 버전이 대상 컴파일러에서 좋은 코드를 생성하지 않는 경우 inline-asm보다 훨씬 좋습니다. 내가 아는 컴파일러에는 크로스 플랫폼 내장 함수가 없습니다. 다음은 몇 가지 x86 옵션입니다.
- 인텔 문서가
<immintrin.h>제공_rotl하고_rotl64내장 및 오른쪽 시프트에 대한 동일. MSVC에는<intrin.h>, gcc에는<x86intrin.h>. 는#ifdefGCC 대 ICC을 담당하지만, 그 소리는 어디를 제공하지 않는 것 와 MSVC 호환성 모드를 제외하고-fms-extensions -fms-compatibility -fms-compatibility-version=17.00. 그리고 그것이 그들을 위해 방출하는 asm은 짜증납니다 (추가 마스킹 및 CMOV). - MSVC :
_rotr8및_rotr16. - GCC 및 ICC (연타되지 않음)
<x86intrin.h>도 제공__rolb/__rorb8 비트 회전 / 좌우위한__rolw/__rorw(16 비트)__rold/__rord(32 비트)__rolq/__rorq(64 비트, 64 비트 타겟 정의). 좁은 회전의 경우 구현에서__builtin_ia32_rolhior를 사용...qi하지만 32 및 64 비트 회전은 shift / or를 사용하여 정의됩니다 (의 코드는ia32intrin.hx86의 gcc에서만 작동해야 하므로 UB에 대한 보호 기능 없음 ). GNU C__builtin_rotate는__builtin_popcount(단일 명령이 아니더라도 대상 플랫폼에서 최적으로 확장되는) 크로스 플랫폼 기능 이없는 것으로 보입니다 . 대부분의 경우 관용구 인식에서 좋은 코드를 얻습니다.
// For real use, probably use a rotate intrinsic for MSVC, or this idiom for other compilers. This pattern of #ifdefs may be helpful
#if defined(__x86_64__) || defined(__i386__)
#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h> // Not just <immintrin.h> for compilers other than icc
#endif
uint32_t rotl32_x86_intrinsic(rotwidth_t x, unsigned n) {
//return __builtin_ia32_rorhi(x, 7); // 16-bit rotate, GNU C
return _rotl(x, n); // gcc, icc, msvc. Intel-defined.
//return __rold(x, n); // gcc, icc.
// can't find anything for clang
}
#endif
x86이 아닌 일부 컴파일러에도 내장 함수가있을 수 있지만이 커뮤니티 위키 답변을 확장하여 모두 포함하지 않겠습니다. (아마도 intrinsics 에 대한 기존 답변 에서 그렇게 할 수 있습니다 ).
(이 답변의 이전 버전은 MSVC 특정 인라인 asm (32 비트 x86 코드에서만 작동) 또는 C 버전의 경우 http://www.devx.com/tips/Tip/14043 을 제안 했습니다. 댓글은 이에 대한 답변입니다. .)
인라인 asm 은 입력이 저장 / 다시로드되도록 강제하기 때문에 특히 MSVC 스타일 과 같은 많은 최적화 를 무력화 합니다. 신중하게 작성된 GNU C 인라인 asm 회전은 카운트가 컴파일 시간 상수 시프트 카운트에 대한 즉각적인 피연산자가 될 수 있도록 허용하지만 시프트 할 값이 컴파일 타임 상수 인 경우에도 완전히 최적화 할 수 없습니다. 인라인 후. https://gcc.gnu.org/wiki/DontUseInlineAsm .
C ++이므로 인라인 함수를 사용하십시오.
template <typename INT>
INT rol(INT val) {
return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}
C ++ 11 변형 :
template <typename INT>
constexpr INT rol(INT val) {
static_assert(std::is_unsigned<INT>::value,
"Rotate Left only makes sense for unsigned types");
return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}
대부분의 컴파일러에는이를위한 내장 함수가 있습니다. Visual Studio (예 : _rotr8, _rotr16)
확실히 :
template<class T>
T ror(T x, unsigned int moves)
{
return (x >> moves) | (x << sizeof(T)*8 - moves);
}
표준 bitset을 사용하여 어떻게 이런 식으로 ...
#include <bitset>
#include <iostream>
template <std::size_t N>
inline void
rotate(std::bitset<N>& b, unsigned m)
{
b = b << m | b >> (N-m);
}
int main()
{
std::bitset<8> b(15);
std::cout << b << '\n';
rotate(b, 2);
std::cout << b << '\n';
return 0;
}
HTH,
세부적으로 다음 논리를 적용 할 수 있습니다.
비트 패턴이 정수 33602 인 경우
1000 0011 0100 0010
2 개의 오른쪽 shif로 롤오버해야합니다. 먼저 비트 패턴을 복사 한 다음 왼쪽으로 이동합니다. Length-RightShift 즉 길이는 16입니다. 오른쪽 이동 값은 2입니다. 16-2 = 14
14 번 왼쪽 변속 후 얻을 수 있습니다.
1000 0000 0000 0000
이제 33602 값을 필요에 따라 2 번 오른쪽으로 이동합니다. 당신은 얻을
0010 0000 1101 0000
이제 왼쪽으로 이동 한 값의 14 배와 오른쪽으로 이동 한 값의 2 배 사이의 OR을 사용합니다.
1000 0000 0000 0000 0010 0000 1101 0000 =================== 1010 0000 1101 0000 ===================
그리고 이동 된 롤오버 값을 얻습니다. 비트 현명한 작업이 더 빠르며 루프가 필요하지 않습니다.
x가 8 비트 값이면 다음을 사용할 수 있습니다.
x=(x>>1 | x<<7);
L비트 단위로 오른쪽으로 이동 하고 입력 x이 N비트 가있는 숫자 라고 가정합니다 .
unsigned ror(unsigned x, int L, int N)
{
unsigned lsbs = x & ((1 << L) - 1);
return (x >> L) | (lsbs << (N-L));
}
정답은 다음과 같습니다.
#define BitsCount( val ) ( sizeof( val ) * CHAR_BIT )
#define Shift( val, steps ) ( steps % BitsCount( val ) )
#define ROL( val, steps ) ( ( val << Shift( val, steps ) ) | ( val >> ( BitsCount( val ) - Shift( val, steps ) ) ) )
#define ROR( val, steps ) ( ( val >> Shift( val, steps ) ) | ( val << ( BitsCount( val ) - Shift( val, steps ) ) ) )
C ++ 20 std::rotl및std::rotr
도착했습니다! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html<bit> 헤더에 추가해야합니다 .
cppreference는 사용법이 다음과 같을 것이라고 말합니다.
#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>
int main()
{
std::uint8_t i = 0b00011101;
std::cout << "i = " << std::bitset<8>(i) << '\n';
std::cout << "rotl(i,0) = " << std::bitset<8>(std::rotl(i,0)) << '\n';
std::cout << "rotl(i,1) = " << std::bitset<8>(std::rotl(i,1)) << '\n';
std::cout << "rotl(i,4) = " << std::bitset<8>(std::rotl(i,4)) << '\n';
std::cout << "rotl(i,9) = " << std::bitset<8>(std::rotl(i,9)) << '\n';
std::cout << "rotl(i,-1) = " << std::bitset<8>(std::rotl(i,-1)) << '\n';
}
출력 제공 :
i = 00011101
rotl(i,0) = 00011101
rotl(i,1) = 00111010
rotl(i,4) = 11010001
rotl(i,9) = 00111010
rotl(i,-1) = 10001110
지원이 GCC에 도착하면 시도해 보겠습니다. GCC 9.1.0은 g++-9 -std=c++2a여전히 지원하지 않습니다.
제안 내용 :
헤더:
namespace std { // 25.5.5, rotating template<class T> [[nodiscard]] constexpr T rotl(T x, int s) noexcept; template<class T> [[nodiscard]] constexpr T rotr(T x, int s) noexcept;
과:
25.5.5 회전 [bitops.rot]
다음 설명에서 N은를 나타냅니다
std::numeric_limits<T>::digits.template<class T> [[nodiscard]] constexpr T rotl(T x, int s) noexcept;제약 조건 : T는 부호없는 정수 유형 (3.9.1 [basic.fundamental])입니다.
r을 s % N이라고합니다.
반환 값 : r이 0이면 x; r이 양수이면
(x << r) | (x >> (N - r)); r이 음수이면rotr(x, -r).template<class T> [[nodiscard]] constexpr T rotr(T x, int s) noexcept;제약 조건 : T는 부호없는 정수 유형 (3.9.1 [basic.fundamental])입니다. r을 s % N이라고합니다.
반환 값 : r이 0이면 x; r이 양수이면
(x >> r) | (x << (N - r)); r이 음수이면rotl(x, -r).
A std::popcount는 또한 1 비트 수를 계산하기 위해 추가 되었습니다. 32 비트 정수에서 설정 비트 수를 계산하는 방법은 무엇입니까?
소스 코드 x 비트 번호
int x =8;
data =15; //input
unsigned char tmp;
for(int i =0;i<x;i++)
{
printf("Data & 1 %d\n",data&1);
printf("Data Shifted value %d\n",data>>1^(data&1)<<(x-1));
tmp = data>>1|(data&1)<<(x-1);
data = tmp;
}
또 다른 제안
template<class T>
inline T rotl(T x, unsigned char moves){
unsigned char temp;
__asm{
mov temp, CL
mov CL, moves
rol x, CL
mov CL, temp
};
return x;
}
아래는 서명되지 않은 char 및 서명되지 않은 long long 값을 사용하는 이러한 함수 사용법의 데모와 함께 양방향이 구현 된 Dídac Pérez의 답변 의 약간 개선 된 버전입니다 . 몇 가지 참고 사항 :
- 함수는 컴파일러 최적화를 위해 인라인됩니다.
- 나는
cout << +value여기에서 찾은 부호없는 문자를 숫자로 간결하게 출력하기 위해 트릭을 사용했습니다 .https : //stackoverflow.com/a/28414758/1599699 <put the type here>명확성과 안전성을 위해 명시 적 구문을 사용하는 것이 좋습니다 .- 여기 의 추가 세부 정보 섹션에서 찾은 내용 때문에 shiftNum 매개 변수에 부호없는 문자를 사용 했습니다 .
첨가제 표현식 이 음수이거나 첨가제 표현식 이 (승격 된) 시프트 표현식 의 비트 수보다 크거나 같은 경우 시프트 연산의 결과는 정의되지 않습니다 .
사용중인 코드는 다음과 같습니다.
#include <iostream>
using namespace std;
template <typename T>
inline T rotateAndCarryLeft(T rotateMe, unsigned char shiftNum)
{
static const unsigned char TBitCount = sizeof(T) * 8U;
return (rotateMe << shiftNum) | (rotateMe >> (TBitCount - shiftNum));
}
template <typename T>
inline T rotateAndCarryRight(T rotateMe, unsigned char shiftNum)
{
static const unsigned char TBitCount = sizeof(T) * 8U;
return (rotateMe >> shiftNum) | (rotateMe << (TBitCount - shiftNum));
}
void main()
{
//00010100 == (unsigned char)20U
//00000101 == (unsigned char)5U == rotateAndCarryLeft(20U, 6U)
//01010000 == (unsigned char)80U == rotateAndCarryRight(20U, 6U)
cout << "unsigned char " << 20U << " rotated left by 6 bits == " << +rotateAndCarryLeft<unsigned char>(20U, 6U) << "\n";
cout << "unsigned char " << 20U << " rotated right by 6 bits == " << +rotateAndCarryRight<unsigned char>(20U, 6U) << "\n";
cout << "\n";
for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
{
cout << "unsigned char " << 21U << " rotated left by " << +shiftNum << " bit(s) == " << +rotateAndCarryLeft<unsigned char>(21U, shiftNum) << "\n";
}
cout << "\n";
for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
{
cout << "unsigned char " << 21U << " rotated right by " << +shiftNum << " bit(s) == " << +rotateAndCarryRight<unsigned char>(21U, shiftNum) << "\n";
}
cout << "\n";
for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
{
cout << "unsigned long long " << 3457347ULL << " rotated left by " << +shiftNum << " bit(s) == " << rotateAndCarryLeft<unsigned long long>(3457347ULL, shiftNum) << "\n";
}
cout << "\n";
for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
{
cout << "unsigned long long " << 3457347ULL << " rotated right by " << +shiftNum << " bit(s) == " << rotateAndCarryRight<unsigned long long>(3457347ULL, shiftNum) << "\n";
}
cout << "\n\n";
system("pause");
}
--- Substituting RLC in 8051 C for speed --- Rotate left carry
Here is an example using RLC to update a serial 8 bit DAC msb first:
(r=DACVAL, P1.4= SDO, P1.5= SCLK)
MOV A, r
?1:
MOV B, #8
RLC A
MOV P1.4, C
CLR P1.5
SETB P1.5
DJNZ B, ?1
Here is the code in 8051 C at its fastest:
sbit ACC_7 = ACC ^ 7 ; //define this at the top to access bit 7 of ACC
ACC = r;
B = 8;
do {
P1_4 = ACC_7; // this assembles into mov c, acc.7 mov P1.4, c
ACC <<= 1;
P1_5 = 0;
P1_5 = 1;
B -- ;
} while ( B!=0 );
The keil compiler will use DJNZ when a loop is written this way.
I am cheating here by using registers ACC and B in c code.
If you cannot cheat then substitute with:
P1_4 = ( r & 128 ) ? 1 : 0 ;
r <<= 1;
This only takes a few extra instructions.
Also, changing B for a local var char n is the same.
Keil does rotate ACC left by ADD A, ACC which is the same as multiply 2.
It only takes one extra opcode i think.
Keeping code entirely in C keeps things simpler sometimes.
함수 오버로드 :
unsigned int rotate_right(unsigned int x)
{
return (x>>1 | (x&1?0x80000000:0))
}
unsigned short rotate_right(unsigned short x) { /* etc. */ }
#define ROTATE_RIGHT(x) ( (x>>1) | (x&1?0x8000:0) )
참고 URL : https://stackoverflow.com/questions/776508/best-practices-for-circular-shift-rotate-operations-in-c
'Nice programing' 카테고리의 다른 글
| "from : ca n't read / var / mail / Bio"라는 Python 오류가 발생합니다. (0) | 2020.10.04 |
|---|---|
| Oracle 데이터베이스에 허용되는 최대 연결 수를 확인하는 방법은 무엇입니까? (0) | 2020.10.04 |
| SQL Server에서 Group By, having 및 Where 절의 실행 순서는 무엇입니까? (0) | 2020.10.04 |
| JSON 문자열을 이스케이프하는 방법? (0) | 2020.10.04 |
| 코드의 레이아웃 방향 (0) | 2020.10.04 |