# 2020q3 Homework2 (quiz2)
contributed by < [StoneLin0708](https://github.com/StoneLin0708) >

###### tags: `sysprog2020`

# is_ascii

bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & 0x8080808080808080)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

Since one byte solution is using bitwise AND to detect the 8th bit,
eight byte should do the similiar, so the mask is:
0x8080 8080 8080 8080
||binary|
|-|-|
|char|zxxx xxxx|
|0x80|1000 0000|
|result|z000 0000|

### Question

* Q: Why memcpy?
A: memcpy is to make sure it copy rest 7 char after, using cast could result at copy rest 7 char before address.
* Q: Implement is_alphabet

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

bool is_alphabet(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        payload |= PACKED_BYTE(0x20);
        uint64_t a_check = payload + PACKED_BYTE(0x80 - 'a');
        uint64_t z_check = payload + PACKED_BYTE(0x80 - 'z' - 1);
        if ((a_check ^ z_check) & PACKED_BYTE(0x80) ^ PACKED_BYTE(0x80))
            return false;
        i += 8;
    }
    while (i < size) {
        const char c = str[i] | 0x20;
        if (c < 'a' || c > 'z')
            return false;
        i++;
    }
    return true;
}

Packed byte from test5 help a lot fot solving this, after tolower, detect the chars in range between 'a' - 'z' also by method from test5.

# hexchar2val

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

The return value give a nice hint, shift must be 10 if `in` is a hex character.
|char|hex|bin|
|-|-|-|
|'0'|0x30|0011 0000
|'9'|0x39|0011 1001

MASK is to extract some pattern and convert to 10 (1010)

|char|hex|bin|
|-|-|-|
|'A'|0x41|0100 0001|
|'Z'|0x5A|0101 1010|
|'a'|0x61|0110 0001|
|'z'|0x7A|0111 1010|

||hex|bin|
|-|-|-|
|MASK|0x40|0100 0000|
|10 |0x0A|0000 1010|

Shift mask for 3 and 5 bit to get 10.

# quickmod

### I don't know how it work at all

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

/* 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;
}

$\dfrac{n}{d}=\dfrac{2^Nn}{2^Nd}=n\dfrac{\dfrac{2^N}{d}}{2^N}=n({\dfrac{2^N}{d}}>>N)$

$n = q * d + r$

$q = n(M>>N), M = \dfrac{2^N}{d}$

$n\mod d\\
= r\\
= n - q \times d\\
= n - n(M>>N) \times d$

# divisible

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

$n\mod d\\
= r\\
= n - q \times d\\
= n - n(M>>N) \times d = 0$

$=> n - n(M>>N) \times d = 0\\
=> n = n(M>>N) \times d\\
=> 1 = (M>>N) \times d$

# strlower

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

PACKED_BYTE is to repeat `b` for 8 times.

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]);
    }
}

/* 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(0x80)) == 0) { /* is ASCII? */

Calculate distance to 'A' and distance to 'Z'.
The MSB (extended to every byte in word by packed byte) of byte is set if the value greater than 'A', 'Z'.

            uint64_t A = *chunk + PACKED_BYTE(128 - 'A'); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' - 1);

Detect upper and apply mask to result.
||binary|
|-|-|
|Upper|110* ****|
|0x80|1000 0000|
|>>2|0010 0000|
|0x60|0110 0000|
|0x40|0100 0000|

            uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80)) >> 2;
            *chunk ^= mask;

        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

# singleNumber

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

|h|l|x|h^x|l^x|~h|~l|h'|l'|state|
|-|-|-|-|-|-|-|-|-|-|
|0|0|0|0|0|1|1|0|0|keep|
|0|1|0|0|1|1|0|0|1|keep|
|1|0|0|1|0|0|1|1|0|keep|
|0|0|1|1|1|1|1|0|1|next|
|0|1|1|1|0|1|0|1|0|next|
|1|0|1|0|1|0|1|0|0|next|

Observation from truth table:
* Only when a bit is set, the state change to next.
* There are three state in total

In the other world, it clear a bit every three times, and the answer is the left over after all input sequence processed.

### another solution

* count for each bits
* optional times
* pass leetcode runtime limit

int singleNumberN(int* nums, int numsSize, int n){
    int bits = sizeof(int) * 8;
    unsigned res = 0;
    for(int b=0; b < bits; ++b){
        int c=0;
        for(int i=0; i<numsSize; ++i){
            c += (nums[i]>>b) & 0x1;
        }
        res |= (unsigned)(c % n) << b;
    }
    return res;
}

int singleNumber(int* nums, int numsSize){
    return singleNumberN(nums, numsSIze, 3);
}