C의 시프트 연산자를 사용한 곱셈과 나눗셈이 실제로 더 빠릅니까?
예를 들어 비트 연산자를 사용하여 곱셈과 나눗셈을 수행할 수 있습니다.
i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)
기타 등등.
say를 사용하는 요?(i<<3)+(i<<1)을 i*10?? 이런 수 요?이 방법으로 곱하거나 나눌 수 없는 입력이 있습니까?
단답: 그럴리 없습니다.
긴 답변: 컴파일러에는 타겟 프로세서 아키텍처에 가능한 한 빠르게 증식하는 방법을 아는 옵티마이저가 포함되어 있습니다.컴파일러에 자신의 의도를 명확하게 전달하고(즉, i< 1이 아닌 i*2), 가장 빠른 어셈블리/머신 코드 시퀀스를 결정하는 것이 최선입니다.프로세서 자체가 마이크로코드의 일련의 시프트 및 추가로서 멀티플 명령어를 실장했을 가능성도 있습니다.
결론은, 이것에 대해 많은 시간을 소비하지 않는 것입니다.이동하려면 이동해야 합니다.곱셈을 하려면 곱셈을 하세요.의미론적으로 가장 명확한 일을 하세요. 동료들이 나중에 당신에게 고마워할 것입니다.그렇지 않으면 나중에 욕할 수도 있습니다.
구체적인 측정 기준입니다. 수년 전에 해싱 알고리즘의 두 가지 버전을 벤치마킹했습니다.
unsigned
hash( char const* s )
{
unsigned h = 0;
while ( *s != '\0' ) {
h = 127 * h + (unsigned char)*s;
++ s;
}
return h;
}
그리고.
unsigned
hash( char const* s )
{
unsigned h = 0;
while ( *s != '\0' ) {
h = (h << 7) - h + (unsigned char)*s;
++ s;
}
return h;
}
벤치마킹한 모든 머신에서 첫 번째 머신은 적어도 두 번째 머신만큼 빨랐습니다.다소 의외로, 때로는 더 빨랐습니다(예: Sun Sparc).하드웨어가 고속 곱셈을 지원하지 않는 경우(그리고 대부분의 경우 지원하지 않는 경우), 컴파일러는 곱셈을 적절한 시프트와 추가/하위 조합으로 변환했습니다.또한 최종 목표를 알고 있었기 때문에 사용자가 명시적으로 이동 및 추가/하위를 작성할 때보다 적은 지시로 작업을 수행할 수 있습니다.
15일그 후 컴파일러의 성능이 향상되었기 때문에 컴파일러가 올바르게 동작하고 있는 것을 기대할 수 있습니다(또한 코드가 C'ish인 것은 15년 이상 전의 일이기 때문입니다).는 당연히 ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★.std::string그리고 오늘날에는 반복됩니다.)
여기에 있는 다른 모든 좋은 답변과 더불어, 나눗셈 또는 곱셈을 의미할 때 시프트를 사용하지 않는 또 다른 이유를 지적하겠습니다.나는 곱셈과 덧셈의 상대적 우선순위를 잊어버리고 버그를 도입하는 사람을 본 적이 없다.메인터넌스 프로그래머가 시프트를 통한 '멀티플링'은 논리적으로는 곱셈이지만 구문적으로는 곱셈과 같은 우선순위가 아니라는 것을 잊어버렸을 때 발생하는 버그를 본 적이 있습니다. x * 2 + z ★★★★★★★★★★★★★★★★★」x << 1 + z매우 다르다!
숫자 작업을 하고 있다면 다음과 같은 산술 연산자를 사용합니다.+ - * / %에는 비트 & ^ | >> 있는 섞지 마세요.비트와 산수를 모두 가진 표현은 발생을 기다리고 있는 버그입니다.
실제로 i*10을 직접 사용하는 것보다 say (i<3)+(i<1)를 사용하여 10을 곱하는 것이 더 빠릅니까?
사용하시는 머신에 탑재되어 있을 수도 있고 아닐 수도 있습니다.필요하다면 실제 사용 상황을 측정해 주십시오.
사례 연구 - 486부터 core i7까지
벤치마킹은 의미 있게 하기 매우 어렵지만 몇 가지 사실을 살펴볼 수 있습니다.http://www.penguin.cz/~litarakl/intel/s.html#SAL 및 http://www.penguin.cz/~litarakl/intel/i.html#IMUL에서 산술 시프트와 곱셈에 필요한 x86 클럭 사이클에 대한 아이디어를 얻을 수 있습니다.예를 들어 "486"(최신 목록)을 고수하고 32비트를 등록하여 즉시 실행한다고 가정하면 IMUL은 13-42 사이클, IDIV 44가 소요됩니다.각 SAL은 2에 1을 더하기 때문에 몇 개만 함께 이동해도 겉으로 보기에는 승자처럼 보입니다.
요즘 Core i7을 사용하는 경우:
(http://software.intel.com/en-us/forums/showthread.php?t=61481)에서 입수).
지연 시간은 정수 덧셈의 경우 1사이클, 정수 곱셈의 경우 3사이클입니다.지연시간과 throughput은 http://www.intel.com/products/processor/manuals/에 있는 "Intel®64 and IA-32 Architectures Optimization Reference Manual" 부록 C에서 확인할 수 있습니다.
(일부 인텔 blurb에서)
SSE를 사용하여 Core i7은 추가 및 곱셈 명령을 동시에 발행할 수 있으므로 클럭 사이클당 8개의 부동소수점 연산(FLOP)의 피크 레이트를 얻을 수 있습니다.
그렇게 하면 일이 얼마나 진전되었는지 알 수 있다.- 대 비트시프트 - 비트시프트*90년대 들어서도 심각하게 받아들여졌던 것이 이제는 구식이다.비트 시프트는 여전히 더 빠르지만, 모든 시프트를 수행하고 결과를 더할 때 mul/div의 제곱이 아닌 경우에는 다시 느려집니다. 얻을 수 .모든 영향을 확실하게 수량화하기에는 너무 복잡하지만 대부분은 부정적입니다.
소스 코드 기능 vs 구현
일반적으로 질문에는 C와 C++라는 태그가 붙습니다.제3세대 언어인 이들은 기본 CPU 명령 세트의 세부 정보를 숨기도록 특별히 설계되었습니다.언어 표준을 충족하기 위해서는 기본 하드웨어가 지원하지 않더라도 곱셈 및 시프트 작업을 지원해야 합니다.이러한 경우, 다른 많은 지침을 사용하여 필요한 결과를 합성해야 합니다.마찬가지로 CPU가 부족하고 FPU가 없는 경우 부동소수점 조작을 위한 소프트웨어 지원을 제공해야 합니다.현대판 CPU는 모두 지원합니다.* ★★★★★★★★★★★★★★★★★」<<따라서 이것은 터무니없이 이론적이고 역사적으로 보일 수 있지만 중요한 것은 구현 선택의 자유가 양쪽에 있다는 것입니다.일반적인 경우 CPU가 소스 코드로 요청된 작업을 구현하는 명령을 가지고 있더라도 컴파일러는 원하는 다른 것을 자유롭게 선택할 수 있습니다.왜냐하면 컴파일러가 이 명령어를 사용하는 것이 더 좋기 때문입니다.컴파일러가 직면한 특정 사건입니다
예(가설 어셈블리 언어 사용)
source literal approach optimised approach
#define N 0
int x; .word x xor registerA, registerA
x *= N; move x -> registerA
move x -> registerB
A = B * immediate(0)
store registerA -> x
...............do something more with x...............
exclusive 령는 ())xor코드와는 가 없습니다만, 모든 되기 0 으로할 수 .메모리 주소를 나타내는 소스 코드는, 어떠한 사용도 수반하지 않는 경우가 있습니다.
이런 해킹은 컴퓨터가 있는 동안 오랫동안 사용되어 왔다.3GL의 초기에는 개발자의 이해를 확보하기 위해 컴파일러의 출력이 기존의 하드코어 수작업 최적화 어셈블리 언어 개발 커뮤니티를 만족시켜야 했습니다.이 커뮤니티는 생성된 코드가 느리거나 상세하거나 더 나쁜 것이 아니라는 것입니다.컴파일러는 순식간에 많은 훌륭한 최적화를 도입했습니다.어느 어셈블리 언어 프로그래머보다 뛰어난 중앙 집중식 저장소가 되었습니다만, 특정의 경우에 있어서 중요한 특정의 최적화를 놓칠 가능성은 항상 있습니다.인간이 때때로 그것을 찾아내, 그 결과를 더듬어 찾을 수 있습니다.er 컴파일러는 누군가가 그 경험을 되돌려 줄 때까지 시키는 대로 합니다.
따라서 특정 하드웨어에서 이동 및 추가가 더 빠르더라도 컴파일러 라이터는 안전하고 유익한 타이밍에 정확하게 대처할 수 있을 것입니다.
유지 보수성
하드웨어가 변경되면 다시 컴파일하여 타깃 CPU를 확인하고 다른 최선의 선택을 할 수 있습니다.다만, 「최적화」를 재검토하거나, 곱셈을 사용할 필요가 있는 컴파일 환경과 이행할 필요가 있는 컴파일 환경을 일람표시할 필요는 없습니다.10년 이상 전에 작성된 비비트 시프트의 "최적화"를 생각하면 최신 프로세서에서 실행 중인 코드 속도가 느려집니다.
와 같은 하게 되어 있는 GCC의 경우)에는으로 일련의 비트 될 수 있습니다....main(...) { return (argc << 4) + (argc << 2) + argc; }->imull $21, 8(%ebp), %eax따라서 코드를 수정하지 않아도 재컴파일이 도움이 될 수 있지만 장담할 수는 없습니다.
곱셈이나 나눗셈을 실행하는 이상한 비트쉬프트 코드는 개념적으로 달성하려고 했던 것을 훨씬 덜 표현하기 때문에 다른 개발자들은 혼란스러워하고 혼란스러운 프로그래머는 겉으로 보이는 건전성을 회복하기 위해 버그를 도입하거나 필수적인 것을 제거할 가능성이 높습니다.눈에 잘 띄지 않는 것이 매우 유익할 때만 실행한 후 잘 문서화하면(어쨌든 직관적인 다른 것은 문서화하지 않음) 모든 사람이 행복해질 것입니다.
일반 솔루션과 부분 솔루션
int는 값만 합니다.x,y ★★★★★★★★★★★★★★★★★」z 않고 것을 보다 이러한 한 몇 가지 수 int 다음과 같은 질문을 해 보세요.예를 들어 다음과 같은 질문을 생각해 보겠습니다.
비트 연산자를 사용하여 곱셈 및 나눗셈을 수행할 수 있습니다.
곱셈은 설명하지만 나눗셈은 어때요?
int x;
x >> 1; // divide by 2?
C++ Standard 5.8에 따르면:
- 3 - E1 > > E2 값은 E1 우측 시프트 E2 비트 위치입니다.E1이 부호형이거나 E1이 부호형이면서 음이 아닌 값일 경우, 그 결과는 E1의 몫의 적분을 곱한 E2로 나눈 값이다.E1에 부호 있는 타입과 음의 값이 있는 경우, 결과치는 실장 정의됩니다.
따라서 비트 시프트는 다른 머신에서 동일하게 동작하지 않을 수 있으므로 에 구현 정의 결과가 음수입니다. 단, 훨씬 더 예측 가능하게 동작합니다.(기계에 따라 음수의 표현이 다를 수 있기 때문에 표현을 구성하는 비트의 수가 같아도 범위가 달라지기 때문에 완전히 일관되지 않을 수도 있습니다.
'그냥... 그그int직원의 나이를 저장하는 것입니다. , 그런 계시면, 네, 그런 계시면요.>>컴파일러는 코드 내에서 명시적으로 최적화하지 않는 한 안전한 최적화를 넘길 수 있습니다.그러나, 이러한 통찰을 얻을 수 없기 때문에, 리스크가 높고, 거의 도움이 되지 않습니다.또, 같은 코드로 작업하는 다른 프로그래머는, 취급할 데이터에 대한 비정상적인 기대를 걸고 있는 것을 알 수 없습니다.완전히 안전한 것처럼 보이는 변경은 당신의 "최적화"로 인해 역효과를 가져올 수 있습니다.
이 방법으로 곱하거나 나눌 수 없는 입력이 있습니까?
예... 위에서 설명한 바와 같이 음수는 비트 시프트로 "분할" 때 구현 정의된 동작을 가집니다.
컴파일된 내 머신을 사용해 봤다:
int a = ...;
int b = a * 10;
분해 시 다음과 같은 출력이 생성됩니다.
MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift
이 버전은 순수한 이동 및 추가 기능으로 손으로 최적화된 코드보다 빠릅니다.
컴파일러가 무엇을 생각해낼지 알 수 없기 때문에 단순히 일반적인 곱셈을 쓰고 그가 원하는 방식으로 최적화할 수 있도록 하는 것이 좋습니다.단, 컴파일러가 최적화할 수 없는 매우 정확한 경우는 예외입니다.
시프트 명령과 정수 곱셈 명령어는 대부분의 최신 CPU에서 비슷한 성능을 발휘합니다.정수 곱셈 명령어는 1980년대에는 비교적 느렸지만 일반적으로 이것은 더 이상 사실이 아닙니다.정수 곱셈 명령은 더 높은 지연 시간을 가질 수 있으므로 여전히 시프트가 더 바람직한 경우가 있습니다.더 많은 실행 유닛을 계속 사용할 수 있는 경우에도 마찬가지입니다(단, 이로 인해 양쪽이 절단될 수 있습니다).
그러나 정수 나눗셈은 여전히 느리기 때문에 2의 거듭제곱 대신 시프트를 사용하는 것은 여전히 성공적이며, 대부분의 컴파일러는 이를 최적화로 구현합니다.그러나 이러한 최적화가 유효하려면 배당이 서명되지 않았거나 양수여야 한다. 마이너스 배당의 경우 시프트와 나눗셈이 동일하지 않습니다!
#include <stdio.h>
int main(void)
{
int i;
for (i = 5; i >= -5; --i)
{
printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
}
return 0;
}
출력:
5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3
따라서 컴파일러를 지원하려면 배당 변수 또는 식이 명시적으로 부호화되어 있지 않은지 확인하십시오.
이것은 프로세서와 컴파일러에 따라 다릅니다.일부 컴파일러는 이미 이러한 방식으로 코드를 최적화하고 있지만, 다른 컴파일러는 그렇지 않습니다.따라서 코드를 이렇게 최적화해야 할 때마다 확인해야 합니다.
꼭 최적화할 필요가 없다면 어셈블리 명령이나 프로세서 사이클을 저장하기 위해 소스 코드를 스크램블하지 않을 것입니다.
타깃 디바이스, 언어, 목적 등에 따라 달라집니다.
비디오 카드 드라이버의 픽셀 크런치?그럴 것 같아, 그래!
.NET 비즈니스 어플리케이션 사용하시는 부서용조사할 이유가 전혀 없어요
모바일 기기용 고성능 게임의 경우 검토할 가치가 있을 수 있지만, 보다 쉬운 최적화가 수행된 후에야 가능합니다.
일반적으로 전환은 명령 수준에서 곱하는 것보다 훨씬 빠르지만, 너무 이른 최적화에 시간을 낭비하고 있을 수 있습니다.컴파일러는 컴파일 시에 이러한 최적화를 실행할 수 있습니다.직접 실행해도 가독성에 영향을 미치고 성능에 영향을 주지 않을 수 있습니다.프로파일링에서 이것이 병목현상이라는 것을 알았을 경우에만 이러한 작업을 수행할 수 있습니다.
사실, '마법의 분할'로 알려진 분할 기술은 실제로 엄청난 이익을 창출할 수 있다.다시 한 번 프로파일링을 통해 필요한지를 확인해야 합니다.그러나 그것을 사용하는 경우는, 같은 나눗셈의 의미에 필요한 명령의 파악에 도움이 되는 유용한 프로그램이 있습니다.다음은 예를 제시하겠습니다.http://www.masm32.com/board/index.php?topic=12421.0
MASM32의 OP 스레드에서 꺼낸 예:
include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient
생성 대상:
mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
mul edx
.endif
shr edx,16
반드시 필요한 경우 및 코드 의도를 곱셈/나눗셈이 아닌 전환해야 하는 경우가 아니면 실행하지 마십시오.
평소에는 기계 사이클을 적게 절약할 수 있지만(또는 컴파일러가 최적화를 더 잘 알고 있기 때문에 느슨하게 할 수도 있지만) 비용은 가치가 없습니다.실제 작업이 아닌 사소한 일에 시간을 할애하면 코드를 유지하기가 어려워지고 동료가 욕을 먹게 됩니다.
저장된 각 주기가 실행 시간(분)을 의미하는 고부하 계산의 경우 이 작업을 수행해야 할 수 있습니다.단, 컴파일러의 로직을 실제로 고속화했는지, 고장났는지 확인하기 위해 한 번에 한 곳을 최적화하고 매번 성능 테스트를 실시해야 합니다.
일부 기계에서는 곱셈을 하려면 최대 16에서 32개의 기계 사이클이 필요할 수 있습니다.예, 기계의 종류에 따라 비트 시프트 연산자가 곱셈/나눗셈보다 빠릅니다.
그러나 일부 기계에는 곱셈/나눗셈에 대한 특별한 명령이 포함된 연산 프로세서가 있습니다.
나는 Drew Hall에 의해 표시된 답변에 동의한다.답변에는 몇 가지 추가 노트가 필요할 수 있습니다.
대부분의 소프트웨어 개발자에게 프로세서와 컴파일러는 더 이상 이 문제와 관련이 없습니다.대부분은 8088과 MS-DOS를 훨씬 능가합니다.임베디드 프로세서용으로 아직 개발 중인 사용자에게만 해당될 수 있습니다.
저희 소프트웨어 회사에서는 수학(add/sub/mul/div)을 모든 수학에 사용해야 합니다.데이터 유형 간에 변환할 때는 Shift를 사용해야 합니다(예:n/256이 아닌 n>8로 바이트에 ushort를 지정합니다.
부호 있는 정수와 오른쪽 이동 대 나눗셈의 경우 차이를 만들 수 있습니다.음수일 경우 이동은 음의 무한대로 반올림하는 반면 분할은 0으로 반올림합니다.물론 컴파일러는 나눗셈을 더 저렴한 것으로 변경하지만 변수가 음이 되지 않거나 단순히 상관하지 않는다는 것을 증명할 수 없기 때문에 보통 나눗셈과 같은 반올림 동작을 가진 것으로 변경한다.따라서 숫자가 음수가 아님을 증명할 수 있거나 어느 쪽으로 반올림할지 상관하지 않을 경우 이러한 최적화를 통해 차이를 만들 수 있습니다.
Python은 동일한 난수에 대해 1억 번 동일한 곱셈을 수행합니다.
>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati
>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457
>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758
>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369
따라서 python에서는 곱셈/나눗셈을 2배로 하는 것이 아니라 약간 개선됩니다(나눗셈의 경우 ~10%, 곱셈의 경우 ~1 %)2의 비전력일 경우 상당한 속도 저하가 있을 수 있습니다.
이 #s는 프로세서, 컴파일러(또는 인터프리터--간단함을 위해 python으로 실행)에 따라 달라집니다.
다른 모든 사용자와 마찬가지로 너무 빨리 최적화하지 마십시오.읽기 쉬운 코드를 작성하고 속도가 충분하지 않으면 프로파일을 작성한 다음 느린 부분을 최적화해 보십시오.컴파일러는 사용자보다 최적화에 훨씬 뛰어납니다.
컴파일러가 실행할 수 없는 최적화는 입력이 감소된 경우에만 작동하기 때문입니다.
아래는 64비트의 "Multipliation by the requeral"을 실행하는 더 빠른 나눗셈을 수행할 수 있는 c++ 샘플 코드입니다.분자와 분모는 모두 특정 임계값보다 작아야 합니다.64비트 명령을 사용하여 실제로 일반 눈금보다 더 빠른 속도로 컴파일해야 합니다.
#include <stdio.h>
#include <chrono>
static const unsigned s_bc = 32;
static const unsigned long long s_p = 1ULL << s_bc;
static const unsigned long long s_hp = s_p / 2;
static unsigned long long s_f;
static unsigned long long s_fr;
static void fastDivInitialize(const unsigned d)
{
s_f = s_p / d;
s_fr = s_f * (s_p - (s_f * d));
}
static unsigned fastDiv(const unsigned n)
{
return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc;
}
static bool fastDivCheck(const unsigned n, const unsigned d)
{
// 32 to 64 cycles latency on modern cpus
const unsigned expected = n / d;
// At least 10 cycles latency on modern cpus
const unsigned result = fastDiv(n);
if (result != expected)
{
printf("Failed for: %u/%u != %u\n", n, d, expected);
return false;
}
return true;
}
int main()
{
unsigned result = 0;
// Make sure to verify it works for your expected set of inputs
const unsigned MAX_N = 65535;
const unsigned MAX_D = 40000;
const double ONE_SECOND_COUNT = 1000000000.0;
auto t0 = std::chrono::steady_clock::now();
unsigned count = 0;
printf("Verifying...\n");
for (unsigned d = 1; d <= MAX_D; ++d)
{
fastDivInitialize(d);
for (unsigned n = 0; n <= MAX_N; ++n)
{
count += !fastDivCheck(n, d);
}
}
auto t1 = std::chrono::steady_clock::now();
printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT);
t0 = t1;
for (unsigned d = 1; d <= MAX_D; ++d)
{
fastDivInitialize(d);
for (unsigned n = 0; n <= MAX_N; ++n)
{
result += fastDiv(n);
}
}
t1 = std::chrono::steady_clock::now();
printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);
t0 = t1;
count = 0;
for (unsigned d = 1; d <= MAX_D; ++d)
{
for (unsigned n = 0; n <= MAX_N; ++n)
{
result += n / d;
}
}
t1 = std::chrono::steady_clock::now();
printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);
getchar();
return result;
}
2의 거듭제곱으로 곱하거나 나누기를 원하는 경우에는 컴파일러가 비트 시프트 연산자를 MUL/DIV로 변환해도 문제가 없다고 생각합니다.왜냐하면 일부 프로세서의 마이크로코드(실제로 매크로)가 있기 때문에 특히 시프트 연산자가 1 이상일 경우에는 개선이 이루어지기 때문입니다.또는 보다 명확하게 말하면 CPU에 비트 시프트 연산자가 없는 경우에는 MUL/DIV가 됩니다만, CPU에 비트 시프트 연산자가 있는 경우에는 마이크로 코드브런치를 피합니다.이것은 몇 가지 명령보다 적은 것입니다.
고밀도 바이너리 트리에서 동작하고 있기 때문에 많은 더블/할링 연산을 필요로 하는 코드를 작성하고 있습니다.또, 덧셈보다 최적이라고 생각되는 연산이 하나 더 있습니다.왼쪽(2배수) 시프트와 덧셈입니다.이것은 추가하려는 비트 수보다 시프트가 넓은 경우 왼쪽 시프트 및 xor로 대체할 수 있습니다. 간단한 예는 (i<1)^1로, 2배의 값에 1을 더합니다.왼쪽(리틀 엔디안) 시프트만 공백을 0으로 채우기 때문에 오른쪽 시프트(2 나누기 제곱)에는 물론 적용되지 않습니다.
내 코드에서는 이들 곱셈/나눗셈을 2로 나누어 2연산의 거듭제곱을 매우 집중적으로 사용하고 있으며, 공식은 이미 상당히 짧기 때문에 제거할 수 있는 각 명령어는 상당한 이득이 될 수 있다.프로세서가 이러한 비트 시프트 연산자를 지원하지 않는 경우 이득은 발생하지 않지만 손실은 발생하지 않습니다.
또, 제가 쓰고 있는 알고리즘에서는, 실제로 일어나는 움직임을 시각적으로 표현하고 있습니다.이진 트리의 왼쪽은 더 크고 오른쪽은 더 작습니다.게다가 제 코드에서는 홀수와 짝수는 특별한 의미를 가지며, 나무의 모든 왼손잡이 아이들은 홀수이고, 모든 오른손잡이 아이들과 뿌리는 짝수입니다.아직 접하지 못한 경우도 있지만, 아, 사실 생각지도 못한 일이지만, x&1이 x%2에 비해 더 최적의 연산일 수도 있습니다.짝수일 경우 x&1은 0이 되지만 홀수일 경우 1이 됩니다.
홀수/짝수 식별뿐만 아니라 x&3에 대해 0을 얻으면 4가 우리 숫자의 인수이고 x%7에 대해 8이라는 것도 알 수 있습니다.이러한 케이스는 아마도 제한된 유틸리티를 가지고 있다는 것을 알고 있지만, 모듈러스 연산을 피하고 대신 비트 논리 연산을 사용할 수 있다는 것은 좋은 일입니다.왜냐하면 비트 연산은 거의 항상 가장 빠르고 컴파일러에게는 가장 모호하지 않기 때문입니다.
나는 거의 조밀한 이진수 분야를 발명하고 있기 때문에 사람들이 이 코멘트의 가치를 이해하지 못할 것으로 예상한다.왜냐하면 사람들은 2의 거듭제곱만으로 인수분해를 하거나 2의 거듭제곱/나눗셈만을 하고 싶어하지 않기 때문이다.
실제로 더 빠른지 여부는 실제로 사용되는 하드웨어와 컴파일러에 따라 달라집니다.
gcc 컴파일러의 x+x, x*2 및 x<1 구문의 출력을 비교하면, x86 어셈블리에서 같은 결과를 얻을 수 있습니다.https://godbolt.org/z/JLpp0j
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], edi
mov eax, DWORD PTR [rbp-4]
add eax, eax
pop rbp
ret
따라서 gcc는 입력한 내용과 독립적으로 최적의 솔루션을 결정할 수 있는 현명한 방법입니다.
나도 내가 집을 이길 수 있는지 알고 싶었다. 이것은 임의의 숫자에 대한 더 일반적인 비트 단위 곱셈이다.제가 만든 매크로는 보통보다 약 25~2배 느립니다*.2의 배수에 가깝거나 2의 몇 배수로 구성되면 이길 수 있다고 합니다.(X<4)+(X<2)+(X<2)+(X<1)+X로 구성된 X*65보다 속도가 느립니다.
#include <stdio.h>
#include <time.h>
#define MULTIPLYINTBYMINUS(X,Y) (-((X >> 30) & 1)&(Y<<30))+(-((X >> 29) & 1)&(Y<<29))+(-((X >> 28) & 1)&(Y<<28))+(-((X >> 27) & 1)&(Y<<27))+(-((X >> 26) & 1)&(Y<<26))+(-((X >> 25) & 1)&(Y<<25))+(-((X >> 24) & 1)&(Y<<24))+(-((X >> 23) & 1)&(Y<<23))+(-((X >> 22) & 1)&(Y<<22))+(-((X >> 21) & 1)&(Y<<21))+(-((X >> 20) & 1)&(Y<<20))+(-((X >> 19) & 1)&(Y<<19))+(-((X >> 18) & 1)&(Y<<18))+(-((X >> 17) & 1)&(Y<<17))+(-((X >> 16) & 1)&(Y<<16))+(-((X >> 15) & 1)&(Y<<15))+(-((X >> 14) & 1)&(Y<<14))+(-((X >> 13) & 1)&(Y<<13))+(-((X >> 12) & 1)&(Y<<12))+(-((X >> 11) & 1)&(Y<<11))+(-((X >> 10) & 1)&(Y<<10))+(-((X >> 9) & 1)&(Y<<9))+(-((X >> 8) & 1)&(Y<<8))+(-((X >> 7) & 1)&(Y<<7))+(-((X >> 6) & 1)&(Y<<6))+(-((X >> 5) & 1)&(Y<<5))+(-((X >> 4) & 1)&(Y<<4))+(-((X >> 3) & 1)&(Y<<3))+(-((X >> 2) & 1)&(Y<<2))+(-((X >> 1) & 1)&(Y<<1))+(-((X >> 0) & 1)&(Y<<0))
#define MULTIPLYINTBYSHIFT(X,Y) (((((X >> 30) & 1)<<31)>>31)&(Y<<30))+(((((X >> 29) & 1)<<31)>>31)&(Y<<29))+(((((X >> 28) & 1)<<31)>>31)&(Y<<28))+(((((X >> 27) & 1)<<31)>>31)&(Y<<27))+(((((X >> 26) & 1)<<31)>>31)&(Y<<26))+(((((X >> 25) & 1)<<31)>>31)&(Y<<25))+(((((X >> 24) & 1)<<31)>>31)&(Y<<24))+(((((X >> 23) & 1)<<31)>>31)&(Y<<23))+(((((X >> 22) & 1)<<31)>>31)&(Y<<22))+(((((X >> 21) & 1)<<31)>>31)&(Y<<21))+(((((X >> 20) & 1)<<31)>>31)&(Y<<20))+(((((X >> 19) & 1)<<31)>>31)&(Y<<19))+(((((X >> 18) & 1)<<31)>>31)&(Y<<18))+(((((X >> 17) & 1)<<31)>>31)&(Y<<17))+(((((X >> 16) & 1)<<31)>>31)&(Y<<16))+(((((X >> 15) & 1)<<31)>>31)&(Y<<15))+(((((X >> 14) & 1)<<31)>>31)&(Y<<14))+(((((X >> 13) & 1)<<31)>>31)&(Y<<13))+(((((X >> 12) & 1)<<31)>>31)&(Y<<12))+(((((X >> 11) & 1)<<31)>>31)&(Y<<11))+(((((X >> 10) & 1)<<31)>>31)&(Y<<10))+(((((X >> 9) & 1)<<31)>>31)&(Y<<9))+(((((X >> 8) & 1)<<31)>>31)&(Y<<8))+(((((X >> 7) & 1)<<31)>>31)&(Y<<7))+(((((X >> 6) & 1)<<31)>>31)&(Y<<6))+(((((X >> 5) & 1)<<31)>>31)&(Y<<5))+(((((X >> 4) & 1)<<31)>>31)&(Y<<4))+(((((X >> 3) & 1)<<31)>>31)&(Y<<3))+(((((X >> 2) & 1)<<31)>>31)&(Y<<2))+(((((X >> 1) & 1)<<31)>>31)&(Y<<1))+(((((X >> 0) & 1)<<31)>>31)&(Y<<0))
int main()
{
int randomnumber=23;
int randomnumber2=23;
int checknum=23;
clock_t start, diff;
srand(time(0));
start = clock();
for(int i=0;i<1000000;i++)
{
randomnumber = rand() % 10000;
randomnumber2 = rand() % 10000;
checknum=MULTIPLYINTBYMINUS(randomnumber,randomnumber2);
if (checknum!=randomnumber*randomnumber2)
{
printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
}
}
diff = clock() - start;
int msec = diff * 1000 / CLOCKS_PER_SEC;
printf("MULTIPLYINTBYMINUS Time %d milliseconds", msec);
start = clock();
for(int i=0;i<1000000;i++)
{
randomnumber = rand() % 10000;
randomnumber2 = rand() % 10000;
checknum=MULTIPLYINTBYSHIFT(randomnumber,randomnumber2);
if (checknum!=randomnumber*randomnumber2)
{
printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
}
}
diff = clock() - start;
msec = diff * 1000 / CLOCKS_PER_SEC;
printf("MULTIPLYINTBYSHIFT Time %d milliseconds", msec);
start = clock();
for(int i=0;i<1000000;i++)
{
randomnumber = rand() % 10000;
randomnumber2 = rand() % 10000;
checknum= randomnumber*randomnumber2;
if (checknum!=randomnumber*randomnumber2)
{
printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
}
}
diff = clock() - start;
msec = diff * 1000 / CLOCKS_PER_SEC;
printf("normal * Time %d milliseconds", msec);
return 0;
}
언급URL : https://stackoverflow.com/questions/6357038/is-multiplication-and-division-using-shift-operators-in-c-actually-faster
'programing' 카테고리의 다른 글
| Vue에서 정적 구성 요소를 동적 구성 요소에 추가하는 방법 (0) | 2022.06.07 |
|---|---|
| malloc은 얼라인먼트를 어떻게 이해하나요? (0) | 2022.06.07 |
| Android 가상 장치를 만들 수 없습니다. (0) | 2022.06.06 |
| 메서드의 정적 Import에 적합한 사용 사례는 무엇입니까? (0) | 2022.06.06 |
| "int"와 "unsigned int"의 진정한 차이 (0) | 2022.06.06 |