# Bitwise

> https://hackmd.io/@sysprog/binary-representation#%E8%A7%A3%E8%AE%80%E8%A8%88%E7%AE%97%E6%A9%9F%E7%B7%A8%E7%A2%BC

## NOT operator

x = ~x

## 一補數、二補數
單位元為0，對應到10進制正負換算

x = ~x + 1 // x = -x

| 一補數(無號數/有號數) | 二補數(無號數/有號數) | 2進制 |
| -------- | -------- | -------- |
| 0(+0) | 0 | 0000 |
| 1(1) | 1(1) | 0001 |
| 2(2) | 2(2) | 0010 |
| 3(3) | 3(3) | 0011 |
| 4(4) | 4(4) | 0100 |
| 5(5) | 5(5) | 0101 |
| 6(6) | 6(6) | 0110 |
| 7(7) | 7(7) | 0111 |
| 8(-7) | 8(-8) | 1000 |
| 9(-6) | 9(-7) | 1001 |
| 10(-5) | 10(-6) | 1010 |
| 11(-4) | 11(-5) | 1011 |
| 12(-3) | 12(-4) | 1100 |
| 13(-2) | 13(-3) | 1101 |
| 14(-1) | 14(-2) | 1110 |
| 15(-0) | 15(-1) | 1111 |

## Number of 1 Bits （計算有幾個位元是 1 ）

// __builtin_popcount
// 僅適用32位元無號數
unsigned int count_1_bit(unsigned int x)
{
	x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
	x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
	x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
	x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
	x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
	return x;
}

## Bit Reversal （顛倒位元順序）

// 僅適用32位元無號數
unsigned int bit_reverse(unsigned int x)
{
	x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
	x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
	x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
	x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
	x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
	return x;
}

## Least Significant 1 Bit （找到最低位的 1 ）

int least_significant_1_bit(int x)
{
	return x & -x;
}

## Power of 2 Test （判斷一個正整數是否為 2 的次方）

bool is_power_of_2(int x)
{
	return !(x & (x-1));	// x & (x-1)消去最低位的1
}

## XOR Swap （交換兩個 int 變數）

// 注意：比直接交換還要慢。
void swap(int& x, int& y)
{
	x = x ^ y;
	y = x ^ y;
	x = x ^ y;
}

// 下面的寫法有暫存變數存取順序問題。
// Unspecified Behavior，不同的編譯器可能產生不同結果。
// 千萬不要如此取巧。



void swap(int& x, int& y)
{
	x ^= y ^= x ^= y;
}

void xorSwap(int *x, int *y) 
{
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
}

需要這種手法的情境:
指令集允許 XOR swap 產生較短的編碼 (某些 DSP);
考慮到暫存器數量在某些硬體架構 (如 ARM) 非常有限，register allocation 就變得非常棘手，這時透過 XOR swap 可降低這方面的衝擊;
在微處理器中，記憶體是非常珍貴的資源，此舉可降低記憶體的使用量;
在加解密的實作中，需要常數時間的執行時間，因此保證 swap 兩個數值的執行成本要固定 (取決於指令週期數量);

## Missing Number Problem （檢查缺少的正整數）
陣列放入 1 到 10 的正整數，但是少了一個。找出少了哪一個。
使用 Counting Sort ，雖然時間複雜度低，但是空間複雜度高。

int array[9] = {2, 3, 5, 9, 4, 6, 10, 8, 1};

int find_lack_number()
{
	int n = 0;

	// 1到10全部xor起來
	for (int i=0; i<10; ++i) n ^= i;

	// 陣列裡的數字全部xor起來，與先前結果做xor。
	for (int i=0; i<9; ++i) n ^= array[i];

	return n;
}

## 英文大小寫換算

('a' ^ ' ') // 得到 'A'
('A' ^ ' ') // 得到 'a'

## 取字串，判斷NULL位置

int8_t GetNull(int8_t X)
{
	int8_t temp1, temp2, temp3, temp4;
	int8_t inverse;

	temp1 = (X) - 0x01;	//X為0時，0 - 1 = -1

	inverse = ~(X);	//X為0時，對0做not運算 = -1

	temp2 = temp1 & inverse;	//取前兩個條件相同的地方
	
	temp3 = temp2 & 0x80;	//確認是否為-1

	temp4 = (((X) - 0x01) & ~(X) & 0x80);

	return (((X) - 0x01) & ~(X) & 0x80);
	return (((X) - 0x01010101) & ~(X) & 0x80808080);	//可一次做4個byte
}


## Toggle a bit by XOR

unsigned char c ^= (1 << n);

## XOR 特徵
如大值與小值都為同為正/負整數時做 and bitwise運算。TURE(> 0)，則XOR為大減小。FALSE(== 0)，則XOR為加法。

if(a & b)
{
    int c = a ^ b;    //c = a - b
}
else
{
    int c = a ^ b;    //c = a + b
}


## align up

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
	uintptr_t and_temp;
	uintptr_t xor_temp;
	uintptr_t add_mask;
	uintptr_t not_mask;
	uintptr_t normal_temp;

    if ((alignment & (alignment - 1)) == 0) {  /* Check if alignment is a power of two */
        uintptr_t mask = alignment - 1;		
        //剛好2的指數-1後的值，其二進制都為1。作為判斷是否為2的指數。
        add_mask = (sz + mask);		
        not_mask = ~mask;
        and_temp = add_mask & not_mask;	//捨去alignment位數
        normal_temp = (((sz + mask) / alignment) * alignment);
        return (sz + mask) & ~mask;
        return (((sz + mask) / alignment) * alignment);
    }
    return sz; // Return sz unchanged if alignment is not a power of two
}


## 加法器
> https://kopu.chat/%E4%BB%A5c%E5%AF%A6%E4%BD%9C%E4%BA%8C%E9%80%B2%E4%BD%8D%E5%8A%A0%E6%B3%95/

int add(int a, int b) {
    if (b == 0) return a;
    int sum = a ^ b; /* 相加但不進位 */
    int carry = (a & b) << 1; /* 進位但不相加 */
    return add(sum, carry);
}