Bit Operation 모음 (계속)

bit operation이 모여있는 사이트를 찾았다.

http://graphics.stanford.edu/~seander/bithacks.html

이 사이트에 있는 내용을 남긴다.

 

특정 Value의 sign 값을 찾는 방법

if문을 사용하지 않고 특정 value의 sign을 찾는 방법이다.

(value > 0) - (value < 0) 으로 음수일 경우 -1, 0일경우 0, +1 일경우 +1이 return 되는 방법이다.

const value4 = -1;
const value = 0;
const value2 = 1;
const value3 = 2;

console.log(-(value < 0));
console.log(-(value2 < 0));
console.log(-(value3 < 0));
console.log(-(value4 < 0));
console.log((value3 > 0) - (value3 < 0));
console.log((value > 0) - (value < 0));
console.log((value4 > 0) - (value4 < 0));

 

두개의 Value가 동일한 Sign을 갖는지 확인 하는 방법

두개의 int를 xor하게 되면 맨 앞의 음수값은 1을 갖고 있음으로 무조건 음수가 되게 된다. 무조건 0보다 작음으로 true가 된다. 반대로 두개의 int가 서로 같다면 xor에 따라서 무조건 0보다 크게 된다.

const value4 = -1;
const value5 = -10;
const value = 0;
const value2 = 1;
const value3 = 2;

console.log((value4 ^ value5) < 0); //false
console.log((value2 ^ value3) < 0); //false
console.log((value5 ^ value2) < 0); //true

 

Min, Max Operation

특별한 경우 3항 연산보다 하기가 더 빠르다고 한다. 그런데 일반적으로는 삼항이 더 좋다고 한다.

x < y? y : x;

min : y ^ ((x ^ y) & -(x < y))

max : x ^ ((x ^ y) & -(x < y))

const value4 = -1;
const value5 = -10;
const value = 0;
const value2 = 1;
const value3 = 2;

console.log(value2 ^ ((value3 ^ value2) & -(value3 < value2)));//min
console.log(value3 ^ ((value3 ^ value2) & -(value3 < value2)));//max

 

Bit로 Hashing하기

integer type만 사용 가능한 방법이다.

본 방법은

Single Number II

에서 풀이 방법으로 소개 되었다.

int a = 3이라는 값이 한번 나왔는지 저장하는 방법은 다음과 같다.

int show = 3;
int once = 0;

once = once ^ show; // 000011 = 000000 xor 000011

이경우 once는 3이라는 값이 나왔다는 것을 알 수 있다.

만약에 동일한 값이 2번 나온다면, once에 저장된 값을 삭제하게 된다.

int showDouble = 3;
int once = 0;

once = once ^ showDouble; // 000011 = 000000 xor 000011
once = once ^ showDouble; // 000000 = 000011 xor 000011

위의 방법은 Single Number 문제의 해결 방법이 된다.

만약에 3이 2번 나오고 1이 한번 나오면 최종적으로 1만 남게 된다.

int showDouble = 3;
int once = 0;

once = once ^ showDouble; // 000011 = 000000 xor 000011
once = once ^ showDouble; // 000000 = 000011 xor 000011

int showOnce = 1;
once = once ^ showOnce; // 000001 = 000001 xor 000000

만약에 3이 3번 나오고 1이 한번나왔을 때 1만 남게 하는 방법은 저장을 2번에 걸쳐서 진행해야 한다.

int showDouble = 3;
int once = 0;
int twice = 0;

once = ~twice & (once ^ showDouble); // 000011 = 111111 & (000000 xor 000011)

처음 3이 한번 나왔을 때는 once에 000011이 나오게 된다. 참고로 0의 보수는 111111로 -1의 수로 변경된다.

만약에 2번째 나오게 되면 첫번째 once에서는 3을 삭제하고 twice에 저장을 시켜준다.

int showDouble = 3;
int once = 0;
int twice = 0;
//처음 나왔을 때
once = ~twice & (once ^ showDouble); // 000011 = 111111 & (000000 xor 000011)

//두번째 나왔을 때 기존 저장 되어있던 3 삭제
once = ~twice & (once ^ showDouble); // 000000 = 111111 & (000011 xor 000011)

//두번째 나왔을 때 3저장 가능
twice = ~once & (twice ^ showDouble); // 000011 = 111111 & (000000 xor 000011)

위에 코드를 보면 once는 3이라는 숫자가 2번 나왔음으로 0으로 초기화 되고 twice에서 3이라는 값을 저장할 수 있도록 해준다.

그럼 위에 twice코드가 처음나왔을때도 적용된다면 어떻게 될까?

int showDouble = 3;
int once = 0;
int twice = 0;
//처음 나왔을 때
once = ~twice & (once ^ showDouble); // 000011 = 111111 & (000000 xor 000011)

//처음 나왔을 때
twice = ~once & (twice ^ showDouble); // 000000 = 111100 & (000000 xor 000011)


//두번째 나왔을 때
once = ~twice & (once ^ showDouble); // 000000 = 111111 & (000011 xor 000011)

//두번째 나왔을 때
twice = ~once & (twice ^ showDouble); // 000011 = 111111 & (000000 xor 000011)

처음나왔을 때 twice는 once에서 이미 동일 값을 유지 함으로, 2의 보수 처리로 3이 twice에 저장되지 않게 만들어 주었다.

마지막으로 한번 더 3이 나타나면 어떻게 되는지 확인해 보자.

int showDouble = 3;
int once = 0;
int twice = 0;
//처음 나왔을 때
once = ~twice & (once ^ showDouble); // 000011 = 111111 & (000000 xor 000011)

//처음 나왔을 때
twice = ~once & (twice ^ showDouble); // 000000 = 111100 & (000000 xor 000011)


//두번째 나왔을 때
once = ~twice & (once ^ showDouble); // 000000 = 111111 & (000011 xor 000011)

//두번째 나왔을 때
twice = ~once & (twice ^ showDouble); // 000011 = 111111 & (000000 xor 000011)

//세번째 나왔을 때 -> twice에 이미 값이 있어서 once에 적용될 수 없다.
once = ~twice & (once ^ showDouble); // 000000 = 111100 & (000000 xor 000011)

//세번째 나왔을 때 -> twice에 동일 값이 있음으로 삭제된다.
twice = ~once & (twice ^ showDouble); // 000000 = 111111 & (000011 xor 000011)

위와 같이 3이라는 숫자는 2번 int에 저장이 되고 3번째 나오면서 once, twice에서 모두 삭제되는 모습을 확인 가능하다.