비트 프로그래밍에서 (숫자 및-숫자)는 무엇을 의미합니까?

비트 프로그래밍에서 (숫자 및-숫자)는 무엇을 의미합니까?

---

이 질문에 이미 답변이 있습니다.

• (숫자) & (-숫자)의 의미 3 답변

예를 들면 :

int get(int i) {
    int res = 0;
    while (i) {
        res = (res + tree[i]) % MOD;
        i -= ( (i) & (-i) );
    }
    return res;
}

트리 업데이트 기능 :

void update(int i, int val) {
    while (i <= m) {
        tree[i] = (tree[i] + val) % MOD;
        i += ( (i) & (-i) );
    }
}

를 사용하여 코드에서 무엇을하는지 설명해 주 ( (i) & (-i) )시겠습니까?

---

이 두 함수는 이진 인덱스 트리 (Fenwick 트리) 데이터 구조 의 수정 된 구현입니다 .
다음은 i 변수가 다른 값에 대해 어떻게 업데이트 되는지 보여주는 MikeCAT의 답변을 보완하는 두 개의 그림 입니다.

"get"함수 :
표현의 단순성을 위해 함수 입력의 최대 값이 15라고 가정합니다. 숫자 t 가 있는 노드 는 트리 배열에서 tree [t] 를 나타냅니다 . i 에 대해 get 함수를 호출 하면 반환 된 값은 tree [i]의 합과 배열의 인덱스가 i 의 부모 인 모든 트리 배열 요소의 합입니다.


0을 제외하고 그림에서.
여기 예시들이 있습니다 :

get(15) = tree[15] + tree[14] + tree[12] + tree[8]
get(14) = tree[14] + tree[12] + tree[8]
get(13) = tree[13] + tree[12] + tree[8]
get(12) = tree[12] + tree[8]
get(11) = tree[11] + tree[10] + tree[8]
get(10) = tree[10] + tree[8]
get(9) = tree[9] + tree[8]
get(8) = tree[8]
get(7) = tree[7] + tree[6] + tree[4]
get(6) = tree[6] + tree[4]
get(5) = tree[5] + tree[4]
get(4) = tree[4]
get(3) = tree[3] + tree[2]
get(2) = tree[2]

위의 그림에서 노드의 레이블에있는 숫자는 각 노드의 부모가 노드 레이블에서 최하위 1을 뺀 특성을 갖습니다. 1 (@MikeCAT 답변에 매우 잘 설명 됨) "업데이트"기능 :
그림의 단순성을 위해 가정 해 보겠습니다. 트리 배열 의 최대 길이 는 16입니다
. 업데이트 기능은 약간 까다 롭습니다. 그것은 tree [i] 와 그들의 인덱스가 그림에서 레이블 i 를 가진 노드의 부모 인 모든 트리 요소에 val 을 추가합니다 .

update(16, val) --> tree[16] += val;
update(15, val) --> tree[15] += val, tree[16] += val;
update(14, val) --> tree[14] += val, tree[16] += val;
update(13, val) --> tree[13] += val, tree[14] += val; tree[16] += val;
update(12, val) --> tree[12] += val, tree[16] += val;
update(11, val) --> tree[11] += val, tree[12] += val, tree[16] += val;
update(10, val) --> tree[10] += val, tree[12] += val, tree[16] += val;
update(9, val)  --> tree[9] += val, tree[10] += val, tree[12] += val, tree[16] += val;
update(8, val)  --> tree[8] += val, tree[16] += val;
update(7, val)  --> tree[7] += val, tree[8] += val, tree[16] += val;
update(6, val)  --> tree[6] += val, tree[8] += val, tree[16] += val;
update(5, val)  --> tree[5] += val, tree[6] += val, tree[8] += val, tree[16] += val;
update(4, val)  --> tree[4] += val, tree[8] += val, tree[16] += val;
update(3, val)  --> tree[3] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(2, val)  --> tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(1, val)  --> tree[1] += val, tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;

---

Let me assume that negative value is represented using two's complement. In this case, -i can be calculated as (~i)+1 (flip bits, then add 1).

For example, let me consider i = 44. Then, in binary,

i           = 0000 0000 0000 0000 0000 0000 0010 1100
~i          = 1111 1111 1111 1111 1111 1111 1101 0011
-i = (~i)+1 = 1111 1111 1111 1111 1111 1111 1101 0100
(i) & (-i)  = 0000 0000 0000 0000 0000 0000 0000 0100

As you see, the least bit that is 1 can be calculated using (i) & (-i).

---

In case anyone wanted a more general proof as well,

Assume x has the format a10^k (meaning here, some bitstring a, followed by a 1, followed by k zeroes).

-x is (by definition) the same thing as ~x + 1, so

• x & -x = (fill in)
• a10^k & -(a10^k) = (def. of negation)
• a10^k & ~(a10^k) + 1 = (apply inversion)
• a10 ^k & ~ a01 ^k + 1 = (1 더하기)
• a10 ^k & ~ a10 ^k = (그리고 무언가와 그 반대 사이)
• 0 ^w 10 ^k

그래서 우리는 존재한다고 가정했던 가장 오른쪽에 1 개만 남았습니다.

의 형태에 대한 가정 x의 경우 밖으로 잎 x = 0이 경우 결과는 분명히 아직 제로입니다.

참고 URL : https://stackoverflow.com/questions/35861228/what-does-number-number-mean-in-bit-programming