합해서 특정 값이 되는 경우 찾기

Integer array가 A=[-1, 2, -3, 4]로 주어졌다고 가정하자. 이때 array의 원소 3개를 더해서 특정 값이 되는 경우를 찾고자 한다. 그런데 array의 길이가 길어질수록 계산은 복잡해진다. 따라서 이를 bit값의 형태로 변환하여 array의 원소 중 특정 원소만 찾는 방법으로 생각해본다.

경우의 수를 찾는 방법을 이진법으로 변환

[아이디어 1] 비트 연산자를 사용하여 array 중 특정 규칙에 한해서 선택하는 경우를 모두 찾는다. 
비트 연산자를 활용하는 방법은 다음과 같다.

1 << number

1 * 2^number

1을 number만큼 옮긴 후 빈 공간에는 0을 채움

다시 말해, << 연산자는 a << b 인 경우 첫번째 피 연산자인 a를 b값(2^b)으로 옮기고, 옮긴 후 빈 공간만큼 0을 채우는 것이다. 예를 들자면 , 1 << 5 (1*2^5)는 32를 반환하는 것이다. 무엇보다도 비트 연산자를 활용하여 2의 거듭제곱 값을 구하는 것이 핵심이다. 비트 연산으로 경우의 수를 찾을 것이기 때문에 아이디어로 꼭 필요한 연산이 되겠다.
 
[아이디어 2] 비트 단위로 &연산을 한다.
조건문을 통해 &연산의 결과로 1 또는 0이 나오는 경우를 찾는다. 이때 조건은 다음과 같다.

int bitOperator () {
   if (('외부 반복자의 변수 A' & 1 << '내부 반복자의 변수 B' ) != 0) return 1
   else return 0
}
(ex) 1111 & 0001 = 0001

따라서 integer array의 원소 중 특정 개수를 선택하는 방법에 대해 알아봤다. 이때 특정 경우의 수를 찾기 위한 방법으로는 비트연산자를 사용하고, &연산자로 비트 단위로 연산을 하는 것이다. 이때 비트 연산자의 1의 개수만큼을 찾는 로직을 반복문에 추가하면 원하는 경우의 수를 모두 찾을 수 있을 것이다.
 
참고 페이지 : https://gksid102.tistory.com/90