###### tags: `C/C++` `bitwise`

# C語言: Bitwise Operation
Operator | Function
| --- | --- |
& | AND
\| | OR
^ | XOR
~ | NOT
>> | Right shift
<< | Left shift

## 奇偶數判斷

(x & 1) ? 奇數 : 偶數;

## swap
使用XOR技巧的swap

void swap(int *a, int *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

## 整數加一/減一

-~x  // x = x+1 

~-x // x = x-1  

2's complement of X: -X = ~X+1

## 留下最低位元的值

x & -x

例如：
20(10100)的最低的位元1為4(100)

## 判斷是否為2的次方

int isPower2(int x){
    return x>0 && (x&-x)==x;
}

因為2的次方只會有一個位元1

或者是

int isPower2(int x){
    return x>0 && (x&x-1)==0;
}

## Mask
### Masking bits to 1
使第1個bit為1

flag = 0000_1100
MASK = 0000_0010
flag | MASK = 0000_1110

### Masking bits to 0
使第2個bit為0

flag = 0000_1100
MASK = 0000_0100
flag & ~MASK = 0000_1000

## 消去最低位的1位元
方法一：

x & ( x - 1 )

方法二：

x - ( x & -x)

### 應用
求位元1數量

## 求最高位元的位置
直覺想法：

int highest_bit(unsigned x)
{
    if(x==0) return -1;
    int n = 31;
    while(!(x & 0x80000000)){
        x = x << 1;
        n--;
    }
    return n;
}

二分法：

int highest_bit(unsigned x){
    int n = 31;
    if(x == 0) return -1;
    if((x>>16) == 0) { n = n - 16; x = x << 16;}
    if((x>>24) == 0) { n = n -  8; x = x <<  8;}
    if((x>>28) == 0) { n = n -  4; x = x <<  4;}
    if((x>>30) == 0) { n = n -  2; x = x <<  2;}
    if((x>>31) == 0) { n = n -  1;}
    return n;
}

### 求最低位元
使用技巧(x & -x)留下最低位元，在求最高位元的位置。

## 取出第N位bit的值

int get_N_bit(int x, int n)
{
    return (x >> (n-1)) & 1
}

## References:
[1] http://puremonkey2010.blogspot.com/2011/05/c-bitwise-operation.html
[2] https://blog.kuoe0.tw/posts/2012/01/26/bitwise-operation-utlization/
[3] https://secondcoderlife.blogspot.com/2019/04/cbitwise-operation.html
[4] https://j890111tw.blogspot.com/2019/10/bitwise-operation.html