[java] 비트쉬프트연산자로 부분집합 출력, 갯수세기

 

<< : 왼쪽으로 비트이동, 나머지 부분에 0 채움 (2^n곱함) 4<<2 4 = 0000 0100 -> 0001 0000 -> 16

>> : 오른쪽으로 비트이동, 나머지 부분에 0 채움 (2^n나눔) 4>>1 4 = 0000 0100 -> 0000 0010 -> 2

 

i & (1<<j)  :  i의 j번째비트

v & 1 : 두비트 모두 1일 경우에만 결과가 1

&는 논리곱

 

public class ex_bit {

	public static void main(String[] args) {
		char arr[] = {'A', 'B', 'C', 'D'};
		print(arr, arr.length);
		

	}
	
	public static void print(char[] c, int n) {
		for(int i=0; i <(1<<n); i++) {
			System.out.print("{");
			for(int j=0; j < n; j++) {
				if((i & (1<<j)) != 0)
					System.out.print(c[j]);		
			}
			System.out.println("}");
			System.out.println(count(i));
		}
	}

	public static int count (int v) {
		int count = 0;
		while(v > 0) {
			if((v & 1) == 1) count++;
			v = v >> 1;
		}
		return count;
	}

}

 

결과 :

{}
0
{A}
1
{B}
1
{AB}
2
{C}
1
{AC}
2
{BC}
2
{ABC}
3
{D}
1
{AD}
2
{BD}
2
{ABD}
3
{CD}
2
{ACD}
3
{BCD}
3
{ABCD}
4