[C++] 비트 연산자

비트 연산자

정수 타입의 피연산자에만 적용될 수 있다.

 

기본 원리

• A^B는 값이 같으면 0 다르면 1을 반환한다.
• ~A는 -A-1과 같다.
• 시프트 연산자에서 빈 비트엔 모두 0이 채워지지만 >> 연산자에서 A가 음수인 경우엔 1이 채워진다.

 

문제

https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

카카오 신입 공채 1차 코딩 테스트 문제 해설

#include <iostream>
using namespace std;

int main()
{
	int n = 0;

	cout << "지도 한 변의 크기를 입력해주세요: ";
	cin >> n;

	int* arr1 = new int[n];
	int* arr2 = new int[n];

	cout << "지도 1의 정수 배열을 입력해주세요: ";
	for (int i = 0; i < n; ++i)
		cin >> arr1[i];

	cout << "지도 2의 정수 배열을 입력해주세요: ";
	for (int i = 0; i < n; ++i)
		cin >> arr2[i];

	int* map = new int[n];
	for (int i = 0; i < n; ++i)
		map[i] = arr1[i] | arr2[i];	// 지도 1, 2로 전체 지도 만들기

	int d = 1 << (n - 1);	// n이 4일때, 1000 -> 가장 첫 번째 비트와 and 연산을 하기 위해
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (map[i] & d)
				cout << "#";
			else
				cout << " ";

			map[i] <<= 1;	// 비트 왼쪽으로 1 이동 후 할당
		}
		cout << endl;
	}

	return 0;
}

 

https://www.acmicpc.net/problem/11811

11811번: 데스스타

#include <iostream>
using namespace std;

int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		int a = 0, tmp;
		for (int j = 0; j < N; ++j) {
			cin >> tmp;
			if (i != j)
				a = a | tmp;
		}
		cout << a << " ";
	}

	return 0;
}

 

https://leetcode.com/problems/single-number-ii/description/

LeetCode - The World's Leading Online Programming Learning Platform

#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int first = 0, second = 0;

        for (int i = 0; i < nums.size(); ++i) {
            first = (first ^ nums[i]) & (~second);
            second = (second ^ nums[i]) & (~first);
        }

        return first;
    }
};

 

https://leetcode.com/problems/bitwise-and-of-numbers-range/description/

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        while (left < right)
            right = right & (right - 1);

        return right;
    }
};