[알고리즘][비트연산] 응용 문제 1-1

문제: 임의의 64비트 2진수가 주어지면, 1로 설정된 비트 중 가장 낮은 자리의 오른쪽에 위치하는 모든 비트를 1로 설정하라.

입력 예시: 0100...1000

출력 예시: 0100...1111

 

해설

이 문제는 이진수의 성질을 이용하면 간단히 풀린다.

입력에서 1을 뺀 값을 입력과 OR하면 된다.

입력에서 1을 빼면 가장 낮은 자리의 1이 내림되어 그보다 낮은 자리가 전부 1로 채워지기 때문이다.

public static long carry(long x) {
	return ((x - 1) | x);
}