PINEAL.ME   Archives  About

# Summary of Basic Bit Manipulation

## Count 1 in Binary

1. 每次把各位的数和 1 做 & 运算，然后计数，右移进行下一位。
class Solution {
public:
/**
* @param num: an integer
* @return: an integer, the number of ones in num
*/
int countOnes(int num) {
// write your code here
int counter = 0;
for (int i = 0; i < sizeof(int)*8; i++) {
counter += num & 1;
num >>= 1;
}
return counter;
}
};

1. 把 num 和 num - 1 做 & 运算， 直到num为0，有多少次运算就有多少个1. 因为每次“&”都会去掉num最右边的1.
class Solution {
public:
/**
* @param num: an integer
* @return: an integer, the number of ones in num
*/
int countOnes(int num) {
// write your code here
int counter = 0;
while (num) {
num &= num - 1;
counter++;
}
return counter;
}
};


bool checkPowerOf2(int n) {
// write your code here
return n > 0 && ((n & (n - 1)) == 0);
}


## Flip Bits

class Solution {
public:
/**
*@param a, b: Two integer
*return: An integer
*/
int bitSwapRequired(int a, int b) {
// write your code here
int counter = 0;
int c = a^b;
for (int i = 0; i < 32; i++) {
counter += c & 1;
c >>= 1;
}
return counter;
}
};


## A + B problem

class Solution {
/*
* param a: The first integer
* param b: The second integer
* return: The sum of a and b
*/
public int aplusb(int a, int b) {
while (b != 0) {
int _a = a ^ b;
int _b = (a & b) << 1;
a = _a;
b = _b;
}
return a;
}
};


## Update Bits

Given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e g , M becomes a substring of N located at i and starting at j) You can assume that the bits j through i have enough space to fit all of M. That is, if M=10011， you can assume that there are at least 5 bits between j and i. You would not, for example, have j=3 and i=2, because M could not fully fit between bit 3 and bit 2.

class Solution {
public:
/**
*@param n, m: Two integer
*@param i, j: Two bit positions
*return: An integer
*/
int updateBits(int n, int m, int i, int j) {
// write your code here
int right_part = n & ((1 << i) - 1);
// The behavior of right shift >= 32 is undefined in C++.
int left_part = j >= 31 ? 0 : (n >> (j + 1)) << (j + 1);
return left_part | (m << i) | right_part;
}
};


## swap two variables

void swap(int &a, int &b){
if (a != b){
a ^= b;
b ^= a;
a ^= b;
}
}


## abs

//取符号位
int a = -100;
int i = a >> 31;
//i = 0 正数
if(i == 0){
printf("%d\n",a);
}
//i = 1 负数
else{
printf("%d\n",~a + 1);
}


## Number Complement

class Solution {
public:
int findComplement(int num) {
unsigned mask = ~0;
while (num & mask) mask <<= 1;
return ~mask & ~num;
}
};