# Bit Manipulation ###### tags: `EMBEDDED_C` #### a.基本:set, clear, togger, Bit mask, shift, AND, OR, XOR #### b.應用:有幾個bit為1, Reverse Bit, Bit Swap, Endianess Swap, Little/BIG Endian, Power of Two, 加法器 #### [練習](https://hackmd.io/cxLdBocVTBGIYpapjLkJ7A?view) - [x] set, clear, togger, - [x] shift - [x] AND, OR, XOR - [ ] Bit mask, - [x] 有幾個bit為1(Count leading Bit) - [x] Reverse Bit, - [ ] Bit Swap, - [ ] Little/BIG Endian - [x] Endianess Swap - [x] Power of Two - [ ] Power of Four - [ ] 加法器 ## Uncategory #### [水果] - 什么是大小端存储？ - c中有哪些data type，如果想用一个data type存很多种不同类型的数据应该用什么？ - 设计一个串行协议的时候用大小端的优势和劣势？（这个想多了没答出来其实答案异常简单…） - 写一个函数，用两个长度1byte分别存MSB,LSB。一个长度2byte的变量 把这个值存起来。 - 8-bit process, but how to obtain 16 bit value - 写一个函数去判断系统是大端还是小端 --- ## Basic Bit Manipulation ### Set Bit ```c= ans |= 1U << k; ``` ```c= #define SET_BIT(x, n) (X |= 1U << n) ``` ### Clear bit ```c= ans &= ~(1U << k); ``` ```c= #define CLEAR_BIT(x, n) (x |= ~(1U << n)) ``` ### Check Bit ```c= #define CHECK_BIT(x,n) (((x) & (1 << (n))) != 0) ``` ### Toggloe Bit ```c= ans ^= 1U << k; ``` ```c= #define TOGGLE_BIT(x, n) (x |= ~(1U << n)) ``` ### Reverse Bit * Basic Idea ```c= void reverseBit (uint32_t *p) { while (val) { uint32_t ret = 0; ret = *p & 1; ret = ret << 1; *p = *p >> 1; } *p = ret; } ``` ### 判斷一整數是偶數還是奇數 > 判斷最後一位是 ```c= bool odd_even (uint32_t var) { return (var & 1); } ``` ## Power Of Two * Solution 1 ```clike= bool powerOf2(int var) { if (var > 0) { if((var & var -1) == 0) return true; } return false; } ``` * Solution 2 > 比較快 因為小於等於0可以直接省略 > 注意0不是2的倍數 ```clike= bool isPowerOfTwo(int n){ if (n <= 0) return false; return !(n & (n - 1)); } ``` * Solution3 > true的必要條件 n > 0 && (n & (n-1) == 0) ```clike= bool isPowerOfTwo(int n){ return (n>0&& (n&(n-1))==0)?true:false; } ``` ### 設定一個絕對位址為0x67a9的整數型變數的值為0xaa55 ```c= int *ptr; ptr = (int *)0x67a9; // 設定指標變數的值 *ptr = 0xaa55; //設定指標變數指向的值 ``` --- ### 首先是给一個uint32_t返回32bit中1的個數 e.g請擷取出Input中的第七個bit值? ```clike= int rt_7_bit(uint32_t var) { int ans = 1 & (var >> 6); return ans; } ``` --- ### 取一個 8bit 數值的最低位元位置 最低位元，很有趣，使用 2’s compliment 就可以完成，比如說 >0x34 ``` 0011 0100 2's 1100 1011 + 1 & 1100 1100 --------------------- 0000 0100 ---------> result 這時候我們再用剛剛的找最高位元找出答案就可以了 ``` ```clike= int get_lower_bit_position(unsigned char x) { x = x & (-x); return get_highest_bit_position(x); } ``` --- ### 给一個uint32_t得到32bit中的某一位置1 ```clike= int rt_nth_bit(uint32_t var, int n) { int ans = 1 & (var >> (n-1)); return ans } ``` --- ### 給一個uint32_t 做reverse bit ```clike= uint32_t reverse_bit(uint32_t val) { uint32_t ret = 0; for(int i = 0; i < 32; i++) { ret |= (val & 1); ret = ret << i; val = val >> 1; } return val; } ``` --- ### Trigger the nth * the 13 bit give high! * 0001 0000 0000 0000 * 0X1000 ```clike= Signal = Signal ｜ 0x1000 ``` ```clike= Signal = Signal | (1<<13) ``` --- ### Reverse Endian with 32 bit ```c= uint32_t endian_swap(uint32_t val) { uint32_t swap_val = 0x0; //seperated it for 4 parts swap_val |= (val && 0x000000FF) << 24;//Uisng the bit Mask to get swap_val |= (val && 0x0000FF00) << 8; //Uisng the bit Mask to get swap_val |= (val && 0x00FF0000) >> 8; //Uisng the bit Mask to get swap_val |= (val && 0xFF000000) >> 24;//Uisng the bit Mask to get return swap_val; } ``` ```cpp= Please implement the big/little endian convert uint32_t swap_uint32( uint32_t val ) { val = ((val << 8) & 0xFF00FF00 ) | ((val >> 8) & 0xFF00FF ); return (val << 16) | (val >> 16); } int32_t swap_int32( int32_t val ) { val = ((val << 8) & 0xFF00FF00) | ((val >> 8) & 0xFF00FF ); return (val << 16) | ((val >> 16) & 0xFFFF); } ``` --- ## Big Enidan && Little Endian * Adress from low to high * E.G: `0xFF00AB11` * **Big Endian**越前面放的越重要 | Address | 0x4000 | 0x4001 |0x4002 |0x4003 | -------- | -------- | -------- | --------| --------| | **Byte Order** | byte0 | byte 1|byte 2|byte 3 | **Value** | 0xFF | 0x00|0xAB|0x11| * **Little Endian** ->相反 | Address | 0x4000 | 0x4001 |0x4002 |0x4003 | | -------- | -------- | -------- | --------| --------| | **Byte Order** | byte0 | byte 1|byte 2|byte 3 | **Value** | 0x11 | 0xAB|0x00|0xFF| ### Check Endian(Big / Little) * Method 1 typecasting or shifting ```c= int main(void) { uint32_t u32RawData; uint8_t *pu8CheckData; u32RawData = 0x11223344; //Assign data pu8CheckData = (uint8_t *)&u32RawData; //Type cast /* * We can also shift 24 to seek the last 8bit */ // *pu8CheckData = u32RawData >> 24 if (*pu8CheckData == 0x44) //check the value of lower address { printf("little-Endian"); } else if (*pu8CheckData == 0x11) //check the value of lower address { printf("big-Endian"); } return 0; } ``` * Method 2 Union: ```cpp= typedef union { uint32_t u32RawData; // integer variable uint8_t au8DataBuff[4]; //array of character } RawData; int main(void) { RawData uCheckEndianess; uCheckEndianess.u32RawData = 0x11223344; //assign the value if (uCheckEndianess.au8DataBuff[0] == 0x44) //check the array first index value { printf("little-endian"); } else if (uCheckEndianess.au8DataBuff[0] == 0x11) //check the array first index value { printf("big-endian"); } return 0; } ``` * Method 3 it with C programming ```clike= #include <stdio.h> #include <stdlib.h> #include <stdint.h> union Endian{ char c[64]; uint64_t i; }; // 1 Byte = 8 bit can be expressed 0xFF. int main(void){ union Endian Var; Var.i = (uint64_t)0x11223344;//0x11223344; //(4 + 4 + 4 +4) = 64 bit; printf("sizeof is %ld\n",sizeof(Var.c[0])); printf("The adrees of %p and val is %x \n",&(Var.c[0]),Var.c[0]); printf("The adrees of %p and val is %x \n",&(Var.c[1]),Var.c[1]); printf("The adrees of %p and val is %x \n",&(Var.c[2]),Var.c[2]); printf("The adrees of %p and val is %x \n",&(Var.c[3]),Var.c[3]); if(Var.c[0] == 0x11) printf("Big Endian\n"); else printf("Little Endian\n"); return 0; } ``` --- ## Big/Little Endian convertion https://developer.arm.com/documentation/dui0491/i/Compiler-specific-Features/--rev-intrinsic https://stackoverflow.com/questions/2182002/convert-big-endian-to-little-endian-in-c-without-using-provided-func https://stackoverflow.com/questions/33932038/fast-conversion-of-16-bit-big-endian-to-little-endian-in-arm/33932154 ___ ## Bit Mask ### [Q] 32-bit machine用C語言對位址 0x00005000 的第三個bit設成0，第五個bit設成1？？？ >To Do: 如何 & | 一個val可以直接把這些完成 ```clike= #include <stdio.h> int main() { unsigned int Obj = 0U; unsigned int Addr = 0U; unsigned int * pAddr ; printf("address of obj is %#08x\n", &Obj); scanf("%x", &Addr); pAddr = (unsigned int*)Addr; *pAddr&=(1U<<3) , *pAddr|=~(1U<<5); printf("Obj = %#08x\n", Obj); return 0; } ``` ### Bit Mask * 最右側 3 位設為 1，其餘不變。 * ...0000 0000 0111 ```clike= *val |= 0x7; ``` * 最右側 3 位設為 0，其餘不變 ```clike= *val &= ~(0x7); ``` * 最右側 3 位執行 NOT operator，其餘不變 **觀念**: ### 取一個 8bit 數值的最高位元位置 ### [Q]Bit Wise 比大小 [[Reference](https://www.zhihu.com/question/44356016)] ```clike= int compare(uint32_t a, uint32_t b){ uint32_t diff = a ^ b; //找到兩者間不一樣的bit裡面最左邊那個 if (!diff) return 0; // 001xxxxx -> 00100000 diff |= diff >> 1; diff |= diff >> 2; diff |= diff >> 4; diff |= diff >> 8; diff |= diff >> 16; diff ^= diff >> 1; //最後針對這個最左邊不一樣的bit看看是a擁有還是b擁有 return a & diff ? 1 : -1; } ``` ___ ## SHIFT ___ ## XOR ### [Q]Swap without tmp; >SWAP two number >利用一個特性 a ^ a = 0; b ^ 0 = b; >因此當我們想做交換的時候, 第二行等式 >*b = *a1 ^ *b -> *b = *a ^ *b ^ *a -> > ```c= void swap(uint32_t *a, uint32_t *b) { *a ^= *b; *b ^= *a; *a ^= *b; } ``` --- ## Leetcode: single number https://leetcode.com/problems/single-number/ ___ ## Full Adder ___ ## Counting Bit ### 無號整數裡位元 == 1 的個數 * Solution 1 ```c= int counting_bit(unit32_t var) { int count = 0; while(var > 0) { if ((var & 1) == 1) count++; var = var >> 1; } return count; } ``` ```c= int bitcount(unsigned int x) { int count, i; for(i = 0, count = 0; i < 32; ++i) if((1<<i) & x) ++count; return count; } ``` * solution 2 ```c= int bitcount(unsigned int x) { int count; for(count = 0; x != 0; x &= x - 1) ++count; return count; } ``` ___ ## Reverse Bit ___ ## BIT SWAP ___ ## Reference - [ ] [LeetCode 題型整理](https://darktiantian.github.io/LeetCode%E7%AE%97%E6%B3%95%E9%A2%98%E6%95%B4%E7%90%86%EF%BC%88%E4%BD%8D%E8%BF%90%E7%AE%97%E7%AF%87%EF%BC%89Bit-Manipulation/) - [ ] [Bit Manipulation in C](https://medium.com/techie-delight/bit-manipulation-interview-questions-and-practice-problems-27c0e71412e7) - [ ] [面試經驗談 - C 語言篇](https://goodspeedlee.blogspot.com/2017/09/c.html) - [ ] [[C 語言] Bitwise operation note by Timmy](http://j890111tw.blogspot.com/2019/10/bitwise-operation.html) - [ ] [bitwise operation 面試考題 by暴肝工程司](http://j890111tw.blogspot.com/2019/10/bitwise-operation.html)