흔 한 비트 연산 기법
3490 단어 데이터 구조 와 알고리즘
일부 알고리즘 문제 에서 비트 연산 의 응용 을 볼 수 있다. 컴퓨터 가 비트 연산 을 실행 할 때 속도 가 매우 빠 르 고 비트 연산 의 기 교 를 능숙 하 게 파악 하면 우리 가 프로그램 을 더욱 간결 하고 교묘 하 게 쓰 는 데 도움 이 된다.
1. 어떤 숫자 중 가장 낮은 위 치 를 얻 은 1.
어떤 숫자 에서 가장 낮은 자리 (가장 오른쪽 자리) 의 1 을 표지 로 꺼 내야 할 때 가 있 습 니 다. 어떻게 이 자 리 를 빨리 얻 을 수 있 습 니까?만약 에 우리 가 이때 찾 아야 할 것 이 숫자 k 에서 가장 낮은 1 이 라 고 가정 하면 다음 과 같은 두 가지 방법 이 있다.
방법 1
int flagBit = 1;
while((k & flagBit) == 0) {
flagBit <<= 1;
}
이 를 통 해 알 수 있 듯 이 우 리 는 보조 숫자 인 flagBit 를 사 용 했 습 니 다. 초기 값 은 1 입 니 다. flagBit & k 가 0 이면 왼쪽 으로 한 자 리 를 옮 깁 니 다. 그 중의 1 이 k 에서 가장 낮은 1 과 같은 위치 로 이동 할 때 까지 & 의 결 과 는 0 이 아 닙 니 다.
방법 2
int flagBit = k & (-k);
이 방법 은 가장 간결 한 방법 이 어야 한다. 우 리 는 이 연산 의 논리 적 과정 을 직관 적 으로 생각 할 수 있다. k 를 정수 로 가정 하면 - k 의 원 코드 는 최고 비트 (기호 비트) 와 k 만 다 르 고 반 코드 를 취한 후에 가장 낮은 비트 의 1 은 0 으로 변 하고 더 낮은 비트 는 모두 1 로 변 한다. 다시 코드 를 취 할 때 1 을 추가 해 야 한다. 그러면 원래 의 최저 비트 의 1 은 1 로 변 하고 더 낮은 비트 는 모두 0 으로 변 한다.높 은 자리 와 k 는 모두 반대 되 기 때문에 상 & 후 최 하위 1 을 얻 었 다.문자 서술 이 비교적 거 추 장 스 러 우 니 종이 위 에서 밀어 도 무방 하 다.
k = 8;
k ： 00000000 00000000 00000000 00001000
-k ： 10000000 00000000 00000000 00001000
-k ： 11111111 11111111 11111111 11110111
-k ： 111111111 1111111 11111111 11111000
， 1 ， ， & 1
2. 하나의 수가 2 의 차 멱 인지 판단 합 니 다.
x & (x - 1)
총결산
상술 한 것 은 제 가 현재 만난 기교 일 뿐 입 니 다. 앞으로 문 제 를 푸 는 과정 에서 비트 연산 기 교 를 만나면 저 는 이 글 에 계속 추가 하 겠 습 니 다.만약 본문 이 너 에 게 작은 도움 이 된다 면, 칭찬 을 하고 가도 무방 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
