Duk's Computer science

# 바이너리에서 1인 Bit만 세어보기: Hamming weight(Population count algorithm)

2진수로 바꾸었을때 길이가 n인 정수에서 1인 bit만 세어보는 알고리즘을

발전하는 순서로 나열해 보았습니다.

1. 2로 계속 나누면서 나머지 세기 = O(n)

public static int bitCount1(int i) {
    int count = 0;

    while (i > 0) {
        count += i%2;
        i /= 2;
    }

    return count;
}

2. bit shift 이용해서 1자리 세기 = O(n)

public static int bitCount2(int i) {
    int count = 0;

    while (i> 0) {
        count += 0x1 & i;
        i = i >> 1;
    }

    return count;
}

3-1. Population count 알고리즘으로 풀기 = O(log(n))

public static int bitCount3(int i) {
    i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);        // ...01010101010101010101010101010101...
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);        // ...00110011001100110011001100110011...
    i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);        // ...00001111000011110000111100001111...
    i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);        // ...00000000111111110000000011111111...
    i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);       // ...00000000000000001111111111111111...
    return i & 0x3f;
}

3-2. 고민말고 Integer.bitCount() 쓰기 = O(log(n))

public static int bitCount4(int i) {
    return Integer.bitCount(i);
}

# 1~3 까지의 성능비교

for (int i=0; i < Integer.MAX_VALUE; i++) {
    int a = bitCount(i);
}

4. Hardware 찬스 쓰기

CPU 영역에서 bit를 한번에 세주는 기능이 있다고 한다.

Reference:

- https://en.wikipedia.org/wiki/Hamming_weight

- https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

# Wildcard('?', '*') 패턴 매칭 알고리즘

Wildcard가 들어간 패턴과 주어진 문자가 해당하는지 확인하는 알고리즘 중

매칭테이블로 이를 구현하는 것에 대해 알아본다.

1. 문제의 정의

- "ABC" == "ABC": 문자열 모두 동일하다면 True

- "ABC" == "A?C": 문자열 중 ?가 있는 한글자만 빼고, 나머지는 동일하다면 True

- "AC" == "A*C", "ABBBC" == "A*C": 문자열 중 *가 있는 부분이 없거나 여러개인 경우, 나머지는 동일하다면 True

2. 매칭테이블

Dynamic Programming 기법으로서 이전의 문자열까지의 비교를 누적하고, 다음문자를 비교할때 이를 참고한다.

T(n, m)가 패턴 매칭의 결과가 된다.

3. 매칭의 조건

- case1: text[0] == pattern[0] 이면, T(0,0) = True 라고 본다.

             공백과 공백의 비교는 True라고 본다.

             하지만, 물론, 공백과 공백이 아닌 문자의 비교는 False이다.

- case2: text[i] == pattern[j]  이면, T(i, j) = T(i-1, j-1) 을 따른다.(대각선 상속)

              자기 위치의 문자와, 이전까지 문자열이 매칭되고 있었는지의 누적결과도 확인하는 것이다.

- case3: pattern[j] == ? 이면, T(i, j) = T(i-1, j-1) 을 따른다.(대각선 상속)

              ?의 패턴은 아무문자나 가능하고 그 개수만 맞으면 되기 때문에 이전까지의 누적결과만 확인하면 된다.

- case4: pattern[j] == * 이면, T(i, j) = T(i, j-1) 혹은 T(i-1, j) 을 따른다.(옆 또는 위 상속)

              T(i, j-1) 는 * 의 자리에 특정문자가 추가될 수 있음을 나타내고, 그 이전까지의 누적결과는 괜찮았는지 확인하는 것이다.

              T(i-1, j) 는 * 가 공백에 매칭되고 있음을 나타내고, 그 이전까지의 누적결과는 괜찮았는지 확인하는 것이다.

- case5: pattern[1] == * 이면, T(0, j) = T(0, j-1) 을 따른다.(옆 상속)

              패턴이 *로 시작하면 다음 pattern[2] 까지 문제없음을 전달하기 위함이다.

4. 다양한 case 확인해보기

Reference:

- https://www.geeksforgeeks.org/wildcard-pattern-matching/

- https://www.youtube.com/watch?v=3ZDZ-N0EPV0

# Android Material Design 스크롤에 따라 상단이 접히고 나오는 레이아웃 구성과 역할

화면구성과 그 xml 선언의 관계를 연결해보았습니다.

실제와 다른 부분이 있다면 알려주세요.

적극적으로 검토하고 반영하겠습니다.

Reference

- https://material.io/develop/android/components/collapsing-toolbar-layout/

- https://github.com/chrisbanes/cheesesquare