예를 들어 2의 거듭 제곱 모듈로가 다음과 같이 표현 될 수 있음을 알고 있습니다.
x % 2 inpower n == x & (2 inpower n - 1).
예 :
x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7
두 수의 일반 비 제곱은 어떻습니까?
의 말을하자:
x % 7 ==?
답변
우선, 실제로 그렇게 말하는 것은 정확하지 않습니다.
x % 2 == x & 1
간단한 반례 : x = -1. Java를 포함한 많은 언어에서 -1 % 2 == -1. 즉, %반드시 모듈로의 전통적인 수학적 정의는 아닙니다. 예를 들어 Java는이를 “나머지 연산자”라고 부릅니다.
비트 최적화와 관련하여, 2의 모듈로 거듭 제곱 만이 비트 산술에서 “쉽게”수행 될 수 있습니다. 일반적으로 말하면, b 의 모듈로 거듭 제곱 만이 b 의 숫자 표현으로 “쉽게”수행 될 수 있습니다.
예를 들어, 10 진법에서 음수 가 아닌 N경우 N mod 10^k는 최하위 k숫자 만 사용합니다.
참고 문헌
답변
답변
이진 표현에서 1 비트 만 ‘1’로 설정되는 고유 한 속성을 갖기 때문에 2의 거듭 제곱 (그리고 종종 양의 값만)에 대해서만 작동합니다. 다른 숫자 클래스는이 속성을 공유하지 않기 때문에 대부분의 모듈러스 식에 대해 비트 및 식을 만들 수 없습니다.
답변
이것은 컴퓨터가 2 진법의 숫자를 나타 내기 때문에 특별히 특별한 경우입니다. 이것은 일반화 가능합니다.
(숫자) base % base x
(number) base 의 마지막 x 자리와 동일 합니다 .
답변
효율적인 알고리즘이 존재하는 2의 거듭 제곱 이외의 모듈 리가 있습니다.
예를 들어 x가 32 비트 unsigned int이면 x % 3 = popcnt (x & 0x55555555)-popcnt (x & 0xaaaaaaaa)
답변
“%”연산자가없는 모듈로 “7”
int a = x % 7;
int a = (x + x / 7) & 7;
답변
&바이너리에서 비트 및 ( ) 연산자를 사용하지 않습니다. 증거 스케치 :
, 그러나 k! = 2 ^ n-1 과 같은 값 k 가 있다고 가정 합니다. 그러면 x == k 이면 표현식 이 “올바르게 작동” 하는 것처럼 보이고 결과는 k 입니다. 이제 x == ki를 고려하십시오 . k에 “0”비트가있는 경우 0보다 큰 i 가 있으며 ki 는 해당 위치에서 1 비트로 만 표현 될 수 있습니다. (예 : 1011 (11)은 100 (4)를 빼면 0111 (7)이되어야하며,이 경우 000 비트는 i = 4 일 때 100이됩니다 .) k 의 식에서 비트 가 0에서 변경되어야하는 경우 기를 나타내는 사람에게x & k == x % (k + 1)x & k, 그러면 x % (k + 1)을 올바르게 계산할 수 없습니다 .이 경우 ki 여야 하지만 비트 부울을 사용하여 마스크가 주어진 값을 생성 할 방법이 없습니다.
