🔍 최하위 켜져 있는 비트 찾기 (S & -S)

최하위에서 가장 먼저 등장하는 1을 찾는 비트 연산자

idx = (S & -S);

🚀 이 연산은 S에서 가장 오른쪽에 위치한 1을 제외한 나머지를 모두 0으로 만든다.

---

✅ 1️⃣ S & -S 연산 과정

📌 핵심 원리

1. -S는 S의 2의 보수(Two's Complement)를 취한 값이다.
   • 2의 보수란 1의 보수(비트 반전) + 1 을 수행한 값.
2. S & -S 연산을 하면 최하위 1만 남고 나머지는 0이 된다.

---

✅ 2️⃣ 예제 분석

예제 1: S = 12 (0b1100)

int S = 12;  // 0b1100
int idx = S & -S;
cout << idx << endl;

✔️ 1단계: S의 2의 보수(-S) 계산

 S  =  0b1100   (12)
~S  =  0b0011   (1의 보수)
+1  =  0b0100   (2의 보수)  -> -S

✔️ 2단계: S & -S 수행

  S   =  0b1100   (12)
- S   =  0b0100   (-12)
----------------------
idx   =  0b0100   (4)

➡ 결과: idx = 4 (0b0100, 최하위 1만 남음!)

---

예제 2: S = 42 (0b101010)

int S = 42;  // 0b101010
int idx = S & -S;
cout << idx << endl;

✔️ 1단계: S의 2의 보수(-S) 계산

 S  =  0b101010  (42)
~S  =  0b010101  (1의 보수)
+1  =  0b010110  (2의 보수)  -> -S

✔️ 2단계: S & -S 수행

  S   =  0b101010  (42)
- S   =  0b010110  (-42)
----------------------
idx   =  0b000010  (2)

➡ 결과: idx = 2 (0b000010, 최하위 1만 남음!)

---

✅ 3️⃣ 최하위 켜져 있는 비트를 찾는 원리

• S & -S는 최하위에서 첫 번째 1을 제외한 나머지를 0으로 만든다.
• 최하위 1을 단독으로 추출하는 것이 필요할 때 사용한다.

---

✅ 4️⃣ 응용: 최하위 1의 위치 찾기

비트 인덱스를 찾으려면 로그 연산(log2) 또는 __builtin_ctz() 함수를 사용 가능

#include <iostream>
using namespace std;

int main()
{
    int S = 42;  // 0b101010
    int lowestBit = S & -S;  // 최하위 1 찾기

    // 최하위 1의 위치 찾기 (0-based index)
    int index = __builtin_ctz(lowestBit);  

    cout << "최하위 1 비트 값: " << lowestBit << endl;
    cout << "최하위 1 비트 위치: " << index << endl;

    return 0;
}

📌 실행 결과

최하위 1 비트 값: 2
최하위 1 비트 위치: 1

✅ 즉, __builtin_ctz(S & -S)를 사용하면 최하위 1의 인덱스를 얻을 수 있어!

---

✅ 5️⃣ 결론

연산 결과

S & -S	최하위 1을 제외한 나머지를 0으로 만든다
__builtin_ctz(S & -S)	최하위 1의 인덱스를 찾는다