Array ( )

Bitmask

2018-12-12 02:06:16 | 조회수 4942


Bitmask 는 1비트의 공간으로 1개의 flag를 표시할 수 있다는 점에서 매우 효율적인 상태 표현 기법이다. 다음과 같은 경우를 보자.


public class Direction {

public boolean mLeft;

public boolean mRight;

public boolean mUp;

public boolean mDown;


public boolean getLeft() {

return mLeft;

}

public boolean setLeft() {

mLeft = mLeft == true ? false : true;

}

/*....*/

}


위의 자바 코드는 방향 state 를 표시하기 위해 4개의 boolean 변수를 사용하고 있다. bitmask 를 이용하도록 변경된 소스를 보자.


public class Direction {

/*LEFT = 1;*/

/*RIGHT = 2;*/

/*UP = 4;*/

/*DOWN = 8;*/

public int mState;


public Direction() {

mState = 0;

}


public boolean getLeft() {

return (mState & 1) == 1;

}

public boolean setLeft(boolean left) {

mState = (mState & 1) == 1 ? mState - 1 : mState + 1;

}

//이하 생략

}


4개의 boolean 변수에서 1개의 int 변수로 동일한 기능을 구현할 수 있음을 알 수 있다. 예제에서는 4개만 다루기 때문에 큰 절감효과가 없지만, 다루는 종류가 많아질 경우 BFS 등의 문제를 풀 때 매우 효율적으로 이용할 수 있다.


Bitmask - 알고리즘닷컴
14 개의 글