Ruby의 Bitwise 해킹

일반적으로 일상 업무에서 비트 단위 수학을 수행할 필요가 없습니다. Ruby의 비트 AND 및 OR 연산자( &및 | )는 아마도 의도보다는 우연히 더 많이 사용됩니다. 누가 실수로 &를 입력하지 않았습니까? 언제 &&를 의미합니까?

그러나 C나 어셈블러와 같은 저수준 언어를 프로그래밍하거나 제 경우에는 Turbo Pascal을 프로그래밍하면서 자랐다면 최소한 약간의 조작은 했을 것입니다.

문제에 대한 Bitwise 솔루션은 훌륭합니다. 컴퓨터가 할 수 있는 가장 기본적인 연산(이진 수학)을 사용하여 문제를 해결할 수 있다면 이보다 더 우아할 수 없습니다.

Ruby에서 바이너리로 작업하기

컴퓨터의 모든 것이 숫자로 표시되고 그 숫자가 이진 형식이라는 것을 알고 있을 것입니다. 하지만 루비에서는 어떻게 생겼습니까? 이 예에서는 Ruby를 사용하여 문자 "a"에 대한 ASCII 문자 코드를 찾은 다음 "바이너리"로 인쇄합니다.

ord를 사용할 수 있습니다. Ruby의 메소드를 사용하여 문자의 ASCII 코드를 가져온 다음 printf 사용 "바이너리" 표현을 인쇄합니다.

숫자를 이진수로 표시하려면 printf와 같은 방법을 사용해야 하지만 항상 이진수였습니다. 0b11111111과 같은 구문을 사용하여 Ruby 코드 내에 이진수를 작성할 수 있습니다. .

이진 리터럴을 코드에 추가하려면 1과 0의 문자열 앞에 0b를 붙입니다. 그래서 0b11111111

이진 값 조작

이제 우리는 루비에서 바이너리 리터럴을 사용하는 방법을 알았으므로 그것들을 가지고 놀 수 있습니다. 이를 위해 비트 연산자를 사용합니다.

&&와 같은 부울 연산자에 익숙할 것입니다. &&b 표현식은 및 b가 모두 true인 경우에만 true를 반환합니다. 비트 연산자는 매우 유사합니다.

예를 들어, 비트 AND는 두 값을 가져와서 비트 단위로 비교합니다. 두 비트가 모두 1이면 해당 출력 비트를 1로 설정하고, 그렇지 않으면 0으로 설정합니다. 따라서 8비트가 있으면 8개의 개별 AND가 발생합니다. 하나의 비트가 있으면 하나의 AND가 있습니다. 다음 예에서는 단일 비트를 사용하여 이를 설명합니다.

단일 비트를 사용한 비트 AND 연산의 예

두 비트에 대해 동일하게 작동합니다.

각 비트 쌍은 개별적으로 anded됩니다.

루비의 비트 연산자

거의 모든 프로그래밍 언어에는 이 비트 연산자 세트가 있습니다. 익숙하지 않다면 IRB에서 약간의 시간을 들여 사용해 보십시오. 한번 배우면 평생 사용할 수 있습니다.

실용적 사용:구성 플래그

좋아, 좋아, 이것은 비트 수학의 가장 지루한 사용이어야 한다. 그러나 그것은 또한 가장 일반적인 것 중 하나입니다. Java, C 또는 C++로 작성된 코드와 인터페이스해야 하는 경우 결국에는 비트 구성 플래그를 보게 될 것입니다.

1996년이고 데이터베이스 시스템을 처음부터 새로 구축했다고 상상해 보십시오. 방금 영화 Hackers를 보았으므로 일종의 액세스 제어를 구축하는 것이 좋을 것이라고 생각합니다.

사용자가 DB에서 수행할 수 있는 8가지 작업(읽기, 쓰기, 삭제 외 5개)이 있습니다. 각각을 독립적으로 설정할 수 있기를 원합니다. 읽을 수는 있지만 쓰거나 삭제할 수는 없는 사용자가 있을 수 있습니다. 테이블을 쓸 수는 있지만 삭제할 수는 없습니다.

이러한 구성 플래그를 저장하는 가장 효율적인 방법은 단일 바이트의 비트로 저장하는 것입니다. 그런 다음 사용자는 단순히 OR을 사용하여 필요한 권한 조합을 생성합니다.

MYDB_READ   = 0b00000001 # These numbers are called bitmasks
MYDB_WRITE  = 0b00000010
MYDB_DELETE = 0b00000100
MYDB_INDEX  = 0b00001000

user.permissions = MYDB_READ | MYDB_WRITE

그건 그렇고, 이것은 유닉스 파일 권한이 처리되는 방식과 정말 유사합니다. 파일을 읽기 전용으로 만들기 위해 매직 넘버를 사용해야 하는 이유가 궁금하시다면 이제 아실 것입니다.

특정 비트가 설정되었는지 감지할 수 없다면 구성 옵션을 비트 단위로 저장하는 것은 그다지 유용하지 않습니다. 그렇게 하려면 비트 AND를 사용하면 됩니다.

비트 마스크와 함께 AND를 사용하여 비트가 설정되었는지 확인합니다.

덜 실용적인 용도(C 프로그래머가 아닌 경우)

이제 수학 마법 같은 일을 해 봅시다.

역사적으로 비트 조작은 일부 계산에서 밀리초의 마지막 부분을 짜내려고 할 때 사용되었습니다. 상상할 수 있듯이 그래픽 프로그래머와 무엇보다 성능이 필요한 사람들이 많이 사용했습니다.

따라서 이와 같은 기술은 일상적인 Ruby 개발에 실용적이지 않습니다. 그러나 여전히 재미있는 학습 활동이며 임베디드 시스템 프로그래밍과 같은 분야에 입문한다면 합법적으로 유용할 수 있습니다. 훨씬 더 철저하게 처리하려면 이 비트 엉뚱한 해킹 목록을 확인하세요.

2의 거듭제곱으로 곱하기 및 나누기

숫자 1, 2, 4, 8의 이진 표현을 살펴보겠습니다. 보시다시피 숫자를 두 배로 늘리는 것은 모든 비트를 왼쪽으로 한 자리 이동하는 것과 같습니다. 마찬가지로 숫자를 반으로 줄이는 것은 오른쪽으로 이동하는 것과 같습니다.

1, 2, 4 8의 이진 표현

기억하시겠지만, 왼쪽 시프트 연산자와 오른쪽 시프트 연산자가 있습니다. 즉, 단순히 비트를 이동하여 2의 거듭제곱으로 곱하고 나눌 수 있습니다.

비트 시프트 연산자를 사용하여 2의 거듭제곱으로 곱하거나 나눌 수 있습니다.

2개의 양의 정수 평균

다음과 같이 두 정수의 기본 덧셈을 수행할 수 있습니다.  (x+y) ==(x&y)+(x|y) ==(x^y)+2*(x&y) 평균을 계산하려면 오른쪽 시프트 연산자를 통해 얻을 수 있는 2로 약간 나누기만 하면 됩니다.

다음과 같이 두 개의 양의 정수를 평균화할 수 있습니다. (x&y)+((x^y)>>1)

빠른 역제곱근

가장 전설적인 예 중 하나를 포함하지 않고 비트 트위들링에 대한 블로그 게시물을 작성할 수 없습니다. 이것은 1999년 Quake 3 경기장 소스 코드에서 가져온 John Carmack의 빠른 역제곱근 근사값입니다. 알고리즘은 그의 것이 아니지만 가장 유명한 구현은 다음과 같습니다.

C에서 Ruby로 직접 변환할 수 없는 방식으로 부동 소수점 숫자의 이진 표현을 구성하여 작동하기 때문에 Ruby로의 직접 이식을 시도하지 않을 것입니다.

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}