# 2020q3 Homework2 (quiz2) contributed by < [StoneLin0708](https://github.com/StoneLin0708) > ###### tags: sysprog2020 # is_ascii c 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 c #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 c 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 c 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 c 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 c #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)  PACKED_BYTE is to repeat b for 8 times. c 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'. c 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| c uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80)) >> 2; *chunk ^= mask;  c } else strlower(s, 8); } k = n % 8; if (k) strlower(s, k); }  # singleNumber c 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 ![](https://i.imgur.com/7MWzq7G.png) c 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); }