[알고리즘 과 데이터 구조] 비트 연산 상식

프로그램의 모든 수 는 컴퓨터 메모리 에 바 이 너 리 로 저장 된다.비트 연산 은 메모리 에 있 는 정수 바 이 너 리 를 직접 조작 하 는 것 이다.비트 연산 을 이해 하면 일부 상황 에서 프로그램의 운행 효율 을 더욱 높 일 수 있 을 뿐만 아니 라 비트 연산 도 알고리즘 을 배 우 는 데 필수 적 인 지식 중 하나 이다.
비트 연산 은 모두 이 진수 에 기초 하여 진행 된다.
논리 와 &
두 자 리 는 모두 1 이 어야 1 이 고, 그렇지 않 으 면 0 이다.
예 를 들 면

	12        ：1100,  
	
	14        : 1110，
	
	          ： 1100.

여 기 는 기억 이 잘 안 나 서 다른 비트 연산 과 헷 갈 리 기 쉽 습 니 다. 자바 의 논리 와 연산 1 은 true 이 고 0 은 false 이 며 모두 true 여야 만 true 라 고 상상 할 수 있 습 니 다.
논리 또는 |
두 분 다 0 이 어야 0 이 고 그렇지 않 으 면 1 입 니 다.
예 를 들 면:

	 6       :  0110
	 
	 8       :  1000 
	 
	         : 1110

기억 방법: 연산 과 의 반작용 으로 볼 수 있다.
논리 이상 또는 ^
같은 것 은 0 이 고 다른 것 은 1 이다. 예 를 들 어:

	8       ： 1000
	
	10       : 1010
	
	        ： 0010

기억 방법: 바 이 너 리 의 무 진 더하기 결과
이 또는 연산 의 법칙: 1, 0 ^ N = = N
2、N ^ N == 0
그래서 이 또는 연산 은 두 개의 다른 수 를 교환 하 는 데 쓸 수 있다.

//                       
int a = x ;
int b = y ;

a = a ^ b;
b = a ^ b; // b = (a ^ b ^ b) = a  
a = a ^ b; // a = (a ^ b ^ a) = b

논리 비 ~
0 은 1, 1 은 0 을 취하 고 2 진 비트 의 모든 수 를 반대로 하 는 것 이 논리 적 비 이다.
예 를 들 면:

	8       : 1000
	         : 0111

변위 < <, > >
< <: 2 진수 왼쪽으로 이동, 높 은 자리 버 리 기, 낮은 자리 0 왼쪽으로 1 위 이동 은 곱 하기 2 에 해당 합 니 다. 예 를 들 어: 8 < 1 결 과 는 0000000 < < 1 결 과 는 00010000 = 16 > >: 2 진수 오른쪽으로 이동, 높 은 자리 0, 낮은 자리 버 리 기.오른쪽으로 1 자 리 를 옮 기 는 것 은 2 를 제외 하 는 것 과 같다. 예 를 들 어 8 > 1 결 과 는 00000000 > > 1 결 과 는 00000100 = 4 이다.
복합 할당 연산
a & b 는 a = a & b 에 해당 합 니 다.
| = 예: a | = b 는 a = a | b 에 해당 합 니 다.
> > = 예: a > > = b 는 a = a > > b 에 해당 한다.
< < = 예: a < < = b 는 a = a <
^ = 예: a ^ = b 는 a = a ^ b 에 해당 합 니 다.
비트 연산 이 프로그램 에서 의 운용
1. 한 개의 수 이 진 비트 의 맨 오른쪽 에 있 는 1 의 이 진 숫자 N & (~ N + 1) 2 를 취하 고 한 배열 에서 한 개의 수 만 홀수 로 나타 나 이 수 를 찾 습 니 다.배열 의 이 수 를 모두 이 또는 연산 하 는데, 마지막 으로 이것 이 홀수 로 나 타 났 다.3. 만약 에 한 배열 에서 두 가지 숫자 가 홀수 번 이 나 타 났 다 면 그 나머지 는 모두 짝수 번 이 나 타 났 고 이 두 개의 홀수 번 이 나 타 났 기 를 바 랍 니 다.

public static  void getOddTimesNum(int[] array){
        int eor = 0;

        /*
                a   b
          ，            ，    a^b
         */
        for(int i = 0; i < array.length; i++) {
            eor ^= array[i];
        }

        //  a ！= b             ，   0，   1，          
        int rightone = eor & (~eor + 1); //       1
        int onlyone=0;
        for(int i = 0; i < array.length ; i++){
        //   ：    1   1，   0      1           0，   rightone，  rightone        1     1，     0.
            if((rightone & array[i]) != 0){
                onlyone ^= array[i];
            }
        }
        System.out.println("onlyone= "+ onlyone + "and anothor= "+ (onlyone ^ eor));

    }