2020q3 Homework2 (quiz2)

contributed by <RusselCK >

tags: `RusselCK`

Q1.判斷指定的記憶體範圍內是否全是有效的 ASCII 字元

目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。

逐一字元比對（效率低）

#include <stddef.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    for (int i = 0; i < size; i++)
        if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */
            return false;
    return true;
}

其中 str 是開頭的記憶體地址， size 則是要檢驗的範圍。

二進位表示 0~127 為 0000 0000~0111 1111 ，也就是說只要第 8 個 bit 為 1 ，該欄位便不為有效的 ASCII 字元
因此，我們可以利用 bitwise 操作（ i.e. if (str[i] & 0x80) ），判別第 8 個 bit 是否為 0

1個 char 的大小 = 1 bytes = 8 bits

0x80 = (1000 0000)₂

在 64 位元的架構下，一次比對 64 位元的資料 (即 word size)

























#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
bool is_ascii(const char str[], size_t size)
{
    // Check size
    if (size == 0)
        return false;
        
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM) // MMM = 0x8080808080808080
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

size_t
- Unsigned integral type
uint64_t
- unsigned integer type with width of exactly 64
void * memcpy ( void * destination, const void * source, size_t num );
- Copy block of memory
- Copies the values of num bytes from the location pointed to by source directly to the memory block pointed to by destination.
Source : http://www.cplusplus.com/

程式碼解析：

    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM) 
            return false;
        i += 8;
    }

64 bits = 8 bytes

每一次迴圈檢查 8 bytes ，memcpy(&payload, str + i, 8); 將起始位址 str + i 後的 8 個 bytes 複製到 payload ，再由 if (payload & MMM) 判斷這 8 個bytes 的每一個 bytes 是否都為有效 ASCII 字元
檢查一個 byte 可以用 & 0x80 來檢查，推理可得，要一次檢查 8 個 bytes ，可以用 & 0x8080808080808080 來檢查
因此， MMM = 0x8080808080808080

    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }

若 size 不為 8 的倍數，前面一個迴圈跳出來後，會剩餘 1~7 個 bytes 沒檢查到
這裡使用傳統方式，一次檢查 1 個 byte

Q1. 進階題

給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母

只要檢測到英文字母，便可return true




























































#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <ctype.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

bool has_alpha(char *s, size_t size)
{
    if (size == 0)
        return false;
        
    for (size_t j = 0; j < size; j++) {
        if ((s[j] >= 'A' && s[j] <= 'Z') || (s[j] >= 'a' && s[j] <= 'z'))
            return true;
   }
   return false;
}

bool has_alpha_vector(char *s, size_t size)
{
    if (size == 0)
        return false;
        
    size_t i = 0;
    while ( (i + 8) <= size){
    
        uint64_t *payload = (uint64_t *) s;

        if ((*payload & PACKED_BYTE(0x80)) == 0) { /* case1 : is ASCII */ 
            
            // Upper mask
            uint64_t A = *payload + PACKED_BYTE(128 - 'A'); 
            uint64_t Z = *payload + PACKED_BYTE(127 - 'Z');
            uint64_t upper_mask = ((A ^ Z) & PACKED_BYTE(0x80));
        
            // Lower mask
            uint64_t a = *payload + PACKED_BYTE(128 - 'a');  
            uint64_t z = *payload + PACKED_BYTE(127 - 'z');
            uint64_t lower_mask = ((A ^ Z) & PACKED_BYTE(0x80));
        
            if ( (upper_mask | lower_mask) & PACKED_BYTE(0x80) )
                return true;
        }else{ /* case 2 */
            if (has_alpha(s, 8))
                return true;
        }
    i += 8;
    s += 8;
    }
    
    i = size % 8;
    if (i){ /* case 3 */
        if (has_alpha(s, 8))
                return true;
    }
        
    return false;
}

此題的運用的技巧及分 case 的方式與 Q5. 類似

#27     while ( (i + 8) <= size)

若最後一組不滿 8 個，則不可進入迴圈，要改使用 case 3

#37            uint64_t upper_mask = ((A ^ Z) & PACKED_BYTE(0x80));

這裡的 mask與 Q5. 不同，是因為不需要改變更動 bits，只須辨別是否為字母即可，因此不需要 >>2
- 若該 byte 為字母，則相對應的 mask 的 byte 為 0x80

承上，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對

提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: Schema Validation with Intel® Streaming SIMD Extensions 4

Q2. 將十六進位表示的字串 (hexadecimal string) 轉為數值

不需要分支 (branchless) 的實作:

已知 in 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。







uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & MASK; // MASK = 0x40
    const uint8_t shift = (letter >> AAA) | (letter >> BBB); 
                          //AAA = 3 、 BBB = 6
    return (in + shift) & 0xf;
}

預期 hexchar2val('F') 和 hexchar2val('f') 回傳 15 = (1111)₂
並且 hexchar2val('0') 回傳 0 = (0000)₂
其他輸入都有對應的數值。

程式碼解析：

考慮以下表格：

Character	Hexdecimal	Binary
F	0x46	0100 0110
f	0x66	0110 0110
0	0x30	0011 0000

我們可以發現，光看第 7 個 bit ，就能夠區分 in 是字母或是數字
我們可以利用 in & (0100 0000) ( i.e. in & 0x40 ) 來達到此效果
- 若 in 為數字，則 letter 為 0x00 = (0000 0000)₂
- 若 in 為字母，則 letter 為 0x40 = (0100 0000)₂
因此， MASK = 0x40

考慮回傳值 (in + shift) & 0xf ：

0xf = (0000 1111)₂

若 in 為 F ， ( f 也可推得相同結果）
- (in + shift) & 0xf = 15
- ( (0100 0110) + shift ) & (0000 1111) = (0000 1111)
- ( (0100 0110) + shift ) = (**** 1111)
- shift = (**** 1001)
若 in 為 0 ，
- (in + shift) & 0xf = 0
- ( (0011 0000) + shift ) & (0000 1111) = (0000 0000)
- ( (0011 0000) + shift ) = (**** 0000)
- shift = (**** 0000)

考慮 shift = (letter >> AAA) | (letter >> BBB) :

若 in 為字母，則 letter 為 (0100 0000)
- 我們可以湊出 AAA = 3 、 BBB = 6 使得答案成立 ( i.e. shift = (**** 1001) )
  - (letter >> AAA) = (letter >> 3) = (0000 1000)
  - (letter >> BBB) = (letter >> 6) = (0000 0001)
若 in 為字母、AAA = 3 、 BBB = 6，則 letter 為 (0000 0000)
- (letter >> AAA) = (letter >> 3) = (0000 0000)
- (letter >> BBB) = (letter >> 6) = (0000 0000)
- 可得 shift = (**** 0000)
因此，AAA = 3 、 BBB = 6

Q2. 進階題

將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值

Hexspeak



























































#include <ctype.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & 0x40; 
    const uint8_t shift = (letter >> 3) | (letter >> 6); 
    return (in + shift) & 0xf;
}

size_t hexspeak2val(char str[]){

    int len = strlen(str);
    assert(len);

    if (len == 1) /* case 1 */ 
        return hexchar2val(str[0]);
    
    assert(str[0] == '0' && (str[1] == 'x' || str[1] == 'X'));

    size_t total = 0;


    size_t i = 2; /* case 2 */
    for (; (i + 8) <= len ; i += 8)
    {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        //printf("%lx\n", payload);
        
        const uint64_t letter = payload & PACKED_BYTE(0x40); 
        const uint64_t shift = (letter >> 3) | (letter >> 6);
        const uint64_t value = (payload + shift) & PACKED_BYTE(0x0f);
        //printf("%lx\n", value);

        //total = total << 64 ;
#if __BYTE_ORDER == __LITTLE_ENDIAN
        for (size_t j = 0; j < 64 ; j += 8)
            total += (( value << j ) >> 56) << (j >> 1);
#else
        for (size_t j = 0; j < 64 ; j += 8)
            total += (( value << j ) >> 56) << ((56 - j) >> 3);
#endif
        //printf("%lx\n",total);
    }
    //printf("%lx\n",total);
    
    for (; i < len ; i++) /* case 3 */
        total = total << 4 | hexchar2val(str[i]));
    //printf("%lx\n",total);

    return total;
}

當加總 total 超過 2^64 - 1 時，會造成 Overflow
- 如果可以解決 Overflow ，加上 #42 total = total << 64 ; ，則可以在更長串的 hexspeak 上執行
目前正在尋找更有效率完成 #44#45、#47#48 之功能的程式碼

若 payload 為 '8BADF00D'
- 在 Little Endian ， value 為 0x0d 00 00 0f 0d 0a 0b 08
- 在 Big Endian ， value 為 0x08 0b 0a 0d 0f 00 00 0d

Q3. 除法運算的改進的策略

將除法改為乘法運算

\frac{n}{d} = \frac{n \times 2^{N}}{d \times 2^{N}} = n \times \frac{\frac{2^{N}}{d}}{2^{N}}

= (n \times \frac{2^{N}}{d}) >> N

其中，

2^{N} / d

可以先算好，節省時間








const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1)) // XXX = 0xFFFFFFFFFFFFFFFF

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n)
{   uint64_t quotient = ((__uint128_t) M * n) >> 64;
    return n - quotient * D;
}

當我們想將 5 除以 4 時，就相當於乘以 0.25，所以我們可將
$5 / 4$ 改為 5×0.25，我們得到整數的部分 (即 1)，和小數部分 (即 0.25)，後者乘以 4 就是 1 ，也就是餘數。

uint64_t
- unsigned integer type with width of exactly 64 bits
  (provided only if the implementation directly supports the type)
UINT64_C
- expands to an integer constant expression having the value specified by its argument and whose type is the promoted type of uint_least64_t
uint_least64_t
- smallest unsigned integer type with width of at least 64 bits
__uint128_t
- GCC extension，用以表示 128 位元的無號數值

程式碼解析：
與數學式對比後，可以發現 N = 64 及 M 應該是擔任
$2^{N} / d$ 的角色，但仍須考量：
- $2^{N} / d$ 可能不整除
- uint64 無法表示小數，
- 應該可以用某些手法來避免上述困擾
因此，可以猜測 XXX 的值應該與
$2^{N}$ 差距不遠，故選 0xFFFFFFFFFFFFFFFF ( i.e.
$2^{N} - 1$ )

證明正確性

0 \leq n - q \times D < D,

w h e r e n, D ϵ N a n d q = ⌊ \frac{n \times (⌊ \frac{2^{N} - 1}{d} ⌋ + 1)}{2^{N}} ⌋, N ϵ N

若已知 n 、 D 為正整數，則存在唯一一組整數解 q 、 r 、且
$0 \leq r < D$ ，使得
$n = q \times D + r$
因此，只要能完成上述證明，便能證明程式的正確性

Q4. 呈 Q3 ，判斷某個數值能否被指定的除數所整除

D 和 M 都沿用 Q3







const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))

bool divisible(uint32_t n)
{
    return n * M <= YYY; // YYY = M-1
}

divisible(7) 要得到 0 (即 7 無法被 3 整除)
divisible(87) 要得到 1 (即白痴是三的倍數)

Q5. 將指定的字串 (或部分字串) 的英文字母全改為小寫

in-place 的實作: (一次比對一個字元)

#include <ctype.h>
#include <stddef.h>
/* in-place implementation for converting all characters into lowercase. */
void strlower(char *s, size_t n)
{
    for (size_t j = 0; j < n; j++) {
        if (s[j] >= 'A' && s[j] <= 'Z')
            s[j] ^= 1 << 5;
        else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */
            s[j] = tolower(s[j]);
    }
}

int tolower ( int c );
- Convert uppercase letter to lowercase (任何語系)
- Converts c to its lowercase equivalent if c is an uppercase letter and has a lowercase equivalent. If no such conversion is possible, the value returned is c unchanged.

向量化 (vectorized) : (一次操作一整個 word )

在 64 位元處理器架構 (以下針對 x86_64, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 x86_64 來說，就是 64 bits，或 8 個位元組)。

























#include <ctype.h>
#include <stddef.h>
#include <stdint.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n)
{
    size_t k = n / 8;
    for (size_t i = 0; i < k; i++, s += 8) {
        uint64_t *chunk = (uint64_t *) s;
        if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

程式碼解析：

#5 #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

0xff = ( 0000 … 0000 1111 1111 )₂

若 b 為 0x * … * cd = ( **** … **** 1011 1100 )₂ ，
則 (uint64_t)(b) & (0xff) 的結果為 ( 0000 … 0000 1011 1100 ) = 0xcd，
即 取出 b 在 16 進制的最後兩位數
0xcd * 0x0101010101010101u 結果為 0xcdcdcdcdcdcdcdcd ，即 將前者複製 8 次

#10     size_t k = n / 8;
#11     for (size_t i = 0; i < k; i++, s += 8) {
#12         uint64_t *chunk = (uint64_t *) s;

8 bytes 一組，共有 k 組需要比對
當然，還有剩餘不滿 8 bytes 的部份，由下一段程式碼處理

case 1 : 8 個 bytes 皆為有效 ASCII 字元

#13         if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */

根據提示，#13 判斷 *chunk 是否為有效的 ASCII 字元 ( 請參考 Q1 )
一次檢查 8 bytes ，因此 PACKED_BYTE(VV1) 必須為 0x8080808080808080
- 若 *chunk & PACKED_BYTE(VV1) 為 0，則 *chunck 8 bytes 皆為有效的 ASCII 字元
故 VV1 = 0x80

#17            *chunk ^= mask;

根據 #17 ，我們可以猜測，程式想用 ('A' ^ ' ') // 得到 'a' 的原理，進行大小寫轉換

' ' = 0x20 = 0010 0000

接下來，們還需要辨別，哪些 bytes 裡頭存放著大寫，找出其在 mask 上的對應位置放上 0x20
反之則為小寫，在 mask 上的對應位置放上 0x00

#16             uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;

若只考慮 1 byte，且該 byte 存放著大寫字母，
則 mask = ((A ^ Z) & VV4 ) >>2 應為 0x20 = ( 0010 0000 )
- ((A ^ Z) & VV4 ) 為 ( 1000 0000 ) = 0x80
若只考慮 1 byte，且該 byte 存放著小寫字母，
則 mask = ((A ^ Z) & VV4 ) >>2 應為 0x00 = ( 0000 0000 )
- ((A ^ Z) & VV4 ) 為 ( 0000 0000 ) = 0x00
綜上所述，我們假設 VV4= 0x80，且
- 若存放著大寫字母，(A ^ Z) 應為 ( 1*** **** )
  - A 應為 ( 1*** **** ) 、 Z 應為 ( 0*** **** )
- 若存放著小寫字母，(A ^ Z) 應為 ( 0*** **** )
  - A 應為 ( 1*** **** ) 、 Z 應為 ( 1*** **** )

#14             uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2);

#14 應該要找出 ASCII 編碼 >= 'A' ( i.e. ( 0100 0001 ) ) 的 bytes
- 128 - 'A' = ( 1000 0000 ) - ( 0100 0001 ) = ( 0011 1111 )
若只考慮 1 byte，且該 byte 存放著大寫字母，
則 *chunk + (128 - 'A' + VV2) = ( 010* **** ) + ( 0011 1111 ) + VV2
- 因為 *chunk 是大寫字母，所以
  - ( 010* **** ) + ( 0011 1111 ) >= 'A' ( 0100 0001 ) + ( 0011 1111 ) = ( 1000 0000 )
  - ( 010* **** ) + ( 0011 1111 ) <= 'Z' ( 0101 1010 ) + ( 0011 1111 ) = ( 1001 1001 )
  - 可達成我們假設的目標：A 應為 ( 1*** **** )
- 因此，假設 VV2 = 0
同理，若存放的是小寫字母， VV2 = 0 也能成立

#15             uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);

#15 應該要找出 ASCII 編碼 <= 'Z' ( i.e. ( 0101 1010 ) ) 的 bytes
- 128 - 'Z' = ( 1000 0000 ) - ( 0101 1010 ) = ( 0010 0110 )
若只考慮 1 byte，且該 byte 存放著大寫字母，
則 *chunk + (128 - 'Z' + VV3) = ( 010* **** ) + ( 0010 0110 ) + VV3
- 因為 *chunk 是大寫字母，所以
  - ( 010* **** ) + ( 0010 0110 ) >= 'A' ( 0100 0001 ) + ( 0010 0110 ) = ( 0110 0111 )
  - ( 010* **** ) + ( 0010 0110 ) <= 'Z' ( 0101 1010 ) + ( 0010 0110 ) = ( 1000 0000 )
  - 除了 'Z' 以外，其他大寫字母都能達成假設的目標：Z 應為 ( 0*** **** )
- 若也要讓 'Z' 達成目標，可以假設 VV3 = -1
同理，若存放的是小寫字母， VV3 = -1 也能成立

case 2 : 8 個 bytes 中，至少有一個不為有效 ASCII 字元

#18           else
#19             strlower(s, 8);

若 *chunk 中有幾個 bytes 不為有效的 ASCII 字元，則無法一次轉換 8 bytes
用傳統方式一次檢查一個 bytes

case 3 : 剩餘不滿 8 個 bytes 的部份

#22     k = n % 8;
#23     if (k)
#24         strlower(s, k);

所有能 8 個 bytes 一組的轉換完之後，可能會有 1~7 個 bytes 尚未轉換
用傳統方式一次檢查一個 bytes

Q5. 進階題

將前述測試程式 `main` 函式的 char `str[]` 更換為 char `*str`，會發生什麼事？

會出現

程式記憶體區段錯誤 (核心已傾印)
Segmentation fault

ISO/IEC 9899:1999 :

§ 6.4 .5 S t r i n g l i t e r a l s

( p.62 )

In translation phase 7, a byte or code of value zero is appended to each multibyte character sequence that results from a string literal or literals.
The multibyte character sequence is then used to initialize an array of static storage duration and length just sufficient to contain the sequence.
For character string literals, the array elements have type char, and are initialized with the individual bytes of the multibyte character sequence; …
It is unspecified whether these arrays are distinct provided their elements have the appropriate values.
If the program attempts to modify such an array, the behavior is undefined.

§ 6.7 .8 E X A M P L E 8

( p.130 )
The declaration

        char s[] = "abc", t[3] = "abc";

defines ‘‘plain’’ char array objects s and t whose elements are initialized with character string literals.

This declaration is identical to

char s[] = { 'a', 'b', 'c', '\0' },
     t[] = { 'a', 'b', 'c' };

The contents of the arrays are modifiable.

On the other hand, the declaration

char *p = "abc";

defines p with type ‘‘pointer to char’’ and initializes it to point to an object with type ‘‘array of char’’ with length 4 whose elements are initialized with a character string literal.

If an attempt is made to use p to modify the contents of the array, the behavior is undefined.

q6. LeetCode 137. Single Number I

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?






int singleNumber(int* nums, int numsSize){
    int note = 0;
    for (int i=0 ; i< numsSize ; i++)
        note ^= nums[i];
    return note;
}

XOR 運算 = 看到 1 就反轉，看到 0 不變
從 bitwise 的角度出發，note 的每個 bit 分別紀錄以檢查的 nums[i] 各 bit 出現 1 的次數
- 若出現次數 mod 2 = 0 ，則 note_i 設為 0
- 若出現次數 mod 2 = 1 ，則 note_i 設為 1
狀態圖：( 圓圈中的值代表 note_i )

Truth table

A	B	C
note_i	num_i	new note_i
0	0	0
0	1	1
1	0	1
1	1	0

$C = 01 + 10$

$= A^{'} B + A B^{'}$

$= A \oplus B$
因此， new note_i = note_i
$\oplus$ num_i

Q6. LeetCode 137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?












int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
        lower &= KKK;   // KKK = ~higher
        higher ^= nums[i];
        higher &= JJJ;  // JJJ = ~lower
    }
    return lower;
}

與 q6 相同概念，不同的是，數字可能出現 1~3 次，需要 lower ( 下方簡稱 L )及 higher ( 下方簡稱 H ) 兩個值來幫忙紀錄：
- 若出現次數 mod 3 = 0 ，則 H_iL_i 設為 00
- 若出現次數 mod 3 = 1 ，則 H_iL_i 設為 01
- 若出現次數 mod 3 = 2 ，則 H_iL_i 設為 10
狀態圖：( 圓圈中的值代表 H_iL_i )

Truth table

A	B	C	D	E
H_i	L_i	num_i	new H_i	new L_i
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	0	0

$E = 001 + 010$

$= A^{'} B^{'} C + A^{'} B C^{'}$

$= A^{'} (B^{'} C + B C^{'})$

$= A^{'} (B \oplus C)$
因此，new L_i = ~ H_i & ( L_i
$\oplus$ num_i )
$D = 001 + 100$

$= A^{'} E^{'} C + A E^{'} C^{'}$

$= E^{'} (A^{'} C + A C^{'})$

$= E^{'} (A \oplus C)$
因此，new H_i = ~ (new L_i) & ( H_i
$\oplus$ num_i )
故，KKK = ~higher 、 JJJ = ~lower

Q6. 進階題

請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時

解法一











int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        int tmp = lower;
        lower ^= nums[i];
        lower &= ~higher;
        higher =  (~higher & tmp & nums[i]) | (higher & ~tmp & ~(nums[i]));
    }
    return lower;
}

Q6. 最後的數學推導中， new H_i 還有另一種寫法：
- $D = 011 + 100$
  
  $= A^{'} B C + A B^{'} C^{'}$
- 因此， new H_i = ( ~ H_i & L_i & num_i ) | ( H_i & ~ L_i & ~ (num_i) )
檢測結果：

解法二： ( 參考 RinHizakura 同學 )

數字只可能出現 1、3 次，可能只需要 note 一個值紀錄即可：
- 若出現次數 mod 3 = 0 or 2 ，則 note_i 設為 0
- 若出現次數 mod 3 = 1 ，則 note_i 設為 1

將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼

重複 4 次 ( 偶數次 )

重複 2的倍數次的情形，都可以使用 q6 的解法
同理，重複 3的倍數次的情形，也都可以使用 Q6 解法

重複 5 次 ( 5的倍數次 )










int singleNumber(int *nums, int numsSize)
{
    int left = 0, middle = 0, right = 0;
    for (int i = 0; i < numsSize; i++) {
        right = ~left & (nums[i] ^ right);
        middle = ~left & ((~right & (middle ^ nums[i])) | (middle & right));
        left = ~middle & ~right & (left ^ nums[i]);
    }
    return right;
}

數字可能出現 1~5 次，需要 left( 下方簡稱 L )、middle( 下方簡稱 M )、right( 下方簡稱 R ) 三個值來幫忙紀錄：
- 若出現次數 mod 5 = 0 ，則 L_iM_iR_i 設為 000
- 若出現次數 mod 5 = 1 ，則 L_iM_iR_i 設為 001
- 若出現次數 mod 5 = 2 ，則 L_iM_iR_i 設為 010
- 若出現次數 mod 5 = 3 ，則 L_iM_iR_i 設為 011
- 若出現次數 mod 5 = 4 ，則 L_iM_iR_i 設為 100
狀態圖：( 圓圈中的值代表 L_iM_iR_i )

Truth table:

A	B	C	D	E	F	G
L_i	M_i	R_i	num_i	new L_i	new M_i	new R_i
0	0	0	0	0	0	0
0	0	0	1	0	0	1
0	0	1	0	0	0	1
0	0	1	1	0	1	0
0	1	0	0	0	1	0
0	1	0	1	0	1	1
0	1	1	0	0	1	1
0	1	1	1	1	0	0
1	0	0	0	1	0	0
1	0	0	1	0	0	0

由上圖的推導，我選擇下列這組解：
- new R_i = ~ L_i & ( R_i
  $\oplus$ num_i )
- new M_i = ~ L_i & ( ( ~ (new R_i) & ( M_i
  $\oplus$ num_i ) ) | ( M_i & new R_i ) )
- new L_i = ~ (new M_i) & ~ (new R_i) & ( L_i
  $\oplus$ num_i )