IT討論區(116) 加拿大救生艇門已開

補充小小。下面係四個有關XOR (^ operator in C/C++) 嘅property

1. a ^ a = 0
2. a ^ 0 = a
3. a ^ b = b ^ a // commutative
4. (a ^ b) ^ c = a ^ (b ^ c) // associative

3 同 4 加埋保證XOR一推數時，次序唔會應響結果。例如
1 ^ 2 ^ 3 ^ 4 = 4 ^ 3 ^ 2 ^ 1 = 1 ^ 4 ^ 2 ^ 3 = 3 ^ 1 ^ 4 ^ 2

如果一堆數目除咗一個單丁外其他係重複，例如：

1，2，3，4，1，3，4

XOR 晒：
1 ^ 2 ^ 3 ^ 4 ^ 1 ^ 3 ^ 4

= 1 ^ 1 ^ 2 ^ 3 ^ 3 ^ 4 ^ 4 // 3. + 4. order does not matter
= (1^ 1) ^ 2 ^ (3 ^ 3) ^ (4 ^ 4)
= 0 ^ 2 ^ 0 ^ 0 // 1. a ^ a = 0
= 2 // 2. a ^ 0 = a

It is extremely inefficient to convert an int to string and then check the digits in string. You can find size of the largest consecutive group of zeroes by shifting and counting.

startup 人工好少，通常要共渡患難，介唔介意講幾多人工

巴打平時去咩網站操sql
唔計leetcode個啲
想要啲by topic 順住操嘅題目

係 呢招第一次睇真係串完之後發現自己都唔係好適合玩 Algo

直接拎個 db 落嚟寫

諗左個變體
Given 4n+3 numbers, all numbers repeat exactly 4 times, except that A appear exactly once and B appear exactly twice
Find A and B

本來想諗啲難啲既變體 但係我自己都未solve到

piece of cake. Solvable in O(n) time and O(1) space. XOR to find A. Then count the number of bits in each bit positions [0,1,...63], assuming sizeof(int) == 8. A bit is set in B iff count is 4n + 2. You can do that in one pass over the data.

Actually, you can skip the XOR and just count the bits in each bit position. A bit is set in A iff count is 4n + 1. bit is set in B iff count is 4n + 2 or 4n + 3.

Since we only care if number of bits modulo 4, bit counting can be done in parallel:

std::vector<int64> a; 

// count[i] store bit count of positions i % 4
// actually 3 is sufficient but 4 is easy to code.
int64 count[4] = {0};

for (int64 a_i : a) {
  // accumulate bit count % 4
  constexpr int64 mask_01 = 0x1111111111111111;
  constexpr int64 mask_11 = 0x3333333333333333;
  for (int i = 0; i < 4; i++) {
    const int64 bits = (a_i >> i) & mask_01;
    count[i] = (count[i] + bits) & mask_11;
  }
}

int64 a = 0, b = 0;
for (int i = 0; i < 4; i++) {
  a |= (count[i] & mask_01) << i;
  b |= ((count[i] >> 1) & mask_01) << i;
}

讀書嘅時候又到

found
https://jorgecandeias.github.io/2019/02/13/algorithm-finding-binary-gaps-in-csharp/
完全唔知c#有<<依種operator

幾乎所有lang都有
btw 技能點完全冇點落algo度

唔錯的 高過fg均價