🔍 최하위 켜져 있는 비트 찾기 (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의 위치 찾기

#include <iostream>
#include <cmath>  // log2 함수 포함
using namespace std;

int main()
{
    int s = 10;  // 0b1010 (십진수 10)
    int a = 15;  // 0b1111 (십진수 15)

    int ind2 = 1;

    s &= ~(1 << ind2);  // 특정 비트를 0으로 만들기
    a ^= (1 << ind2);   // 특정 비트를 토글하기

    int lowInx = (s & -s);  // 최하위 1의 값 찾기

    if (lowInx == 0) {
        cout << "No set bits found!" << endl;
    }
    else {
        int lowIndex = log2(lowInx); // 인덱스 찾기
        cout << "lowest 1's value : " << lowInx << endl;
        cout << "lowest 1's index (log2) : " << lowIndex << endl;
    }

    return 0;
}

📌 실행 결과

lowest 1's value : 8
lowest 1's index (log2) : 3