'Programming Problems/Bit manipulations'에 해당되는 글 2건

Programming Problems/Bit manipulations

같은 갯수의 0과 1을 가지는 바로 더 크고 작은 수를 구하자.

10010


>> 다음 숫자 : 10100

     앞 숫자 : 10001


풀이 : 오른쪽에 1이 있는 첫 0과 그 1을 스왑하면 (반대로 얘기하면 바로 옆이 비어있는 첫 1) 다음 숫자이다.



***

오른쪽이 비어있는 첫 1을 그 오른쪽으로 밀면 바로 작은값

왼쪽이 비어있는 첫 1을 그 왼쪽으로 밀면 바로 큰값

01 >> 큰값

10 >> 작은값


pair<int,int> (int n){

// base cases

if(n==0) return pair<int,int>(0,1);

if(n==-1) return pair<int,int>(-2,0);

int m = 1;

int bigger = 0;

int smaller = 0;

int preflag = m&n;

m = m<<1;

for(int i = 1 ; i < 32 ; i++){

if(preflag!=0&&n&m==0){

// bigger found

bigger = n^(m^(m>>1));

}

if(preflag==0&&n&m!=0){

// smaller found

smaller = n^(m^(m>>1));

}

if(smaller!=0&&bigger!=0) break;

}

return pair<int,int>(smaller,bigger);

}


음수


1101 : -3

1110 : -2(큰값)

1011 : -5(작은값) 

성립한다 !!!


완벽한 알고리즘 ..


time complexity O(logN)

Programming Problems/Bit manipulations

배열에서 3번 중복된 원소들과 한번 등장하는 원소 중에서 하나짜리 찾기

ex ) [2,1,4,5,1,4,2,2,4,1] >> ans : 5


소팅을 해서 찾는다 : O(NlogN), O(1)

해싱을 해서 찾는다 : O(N) O(N)

XOR을 해서 찾는다(?) 비트 문제


비트의 갯수를 세서 확인한다 : O(N), O(1) 그러나 external 메모리를 사용한다..

비트의 갯수 중에서 3의 배수가 아닌 것들을 다 더하면 그게 답이다.


아 이거 맞네.. 근데 그 대신에 전부 센 후에 확인하지 말고 그때그때 3의 배수인지 확인하고 결과값에 더해주면

메모리 사용 안해도 된다..!!


int findtheone(vector<int> & data){

int m = 1;

int ret = 0;

for(int i = 0 ; i < 32 ; i++){

long count = 0;

for(int j = 0 ; j < data.size() ; j++){

count = (count + m&data)%3;

}

ret += count;

m = m<<1;

}

return count;

}