進数システムの概要

コンピュータ科学の基礎として、2進数（バイナリ）、8進数（オクタル）、10進数（デシマル）、16進数（ヘキサデシマル）などの位取り記数法があります。これらはすべて「基数」が異なるだけで、基本的な考え方は共通しています。

各進数での数値表現例（15の場合）

2進数: 1111  
8進数: 17  
10進数: 15  
16進数: F

10進数の理解

10進数では、各桁が右から順に 10⁰, 10¹, 10²... の重みを持ちます。例えば 123 は 1×10² + 2×10¹ + 3×10⁰ です。

2進数の構造

2進数も同様に、右から 2⁰, 2¹, 2²... の重みを持ちます。たとえば 1101₂ = 1×2³ + 1×2² + 0×2¹ + 1×2⁰ = 13 です。

10進数 → 2進数への変換

10進数を2で繰り返し割り、余りを下位ビットから並べることで2進数を得られます。これは基数変換の標準的手法です。

2進数 → 8進数・16進数への変換

• 8進数：2進数を右から3ビットずつ区切り、各ブロックを8進数に変換。例：01101011₂ → 01 101 011 → 153₈
• 16進数：2進数を右から4ビットずつ区切り、各ブロックを16進数に変換。例：01101011₂ → 0110 1011 → 6B₁₆（C言語では 0x6b と表記）

整数の内部表現：原码・反码・補数

符号付き整数は以下の3形式で表現されます：

• 原码（Sign-Magnitude）：最上位ビットが符号（0=正、1=負）、残りが絶対値
• 反码（Ones' Complement）：原码の数値部を全ビット反転
• 補数（Two's Complement）：反码に1を加算

現代のコンピュータでは、補数表現が標準です。理由は以下の通りです：

• 符号ビットと数値部を統一的に扱える
• 加減算を加算回路のみで実現可能（減算 = 補数の加算）
• ゼロの表現が一意（反码では+0と-0が存在）

メモリに格納されるのは常に補数形式です。

ビットシフト演算子

C言語では以下のシフト演算子が利用可能です：

• <<：左シフト（下位ビットに0を詰める）
• >>：右シフト（符号あり整数では算術シフト、符号なしでは論理シフト）

注意点：

• オペランドは整数型に限る
• シフト量が負数またはビット幅以上の場合、動作は未定義

int x = 10;
// x >> -1; // 未定義動作！

ビット単位演算子

以下の演算子は整数の各ビットに対して操作を行います：

• &：AND（両方1なら1）
• |：OR（いずれか1なら1）
• ^：XOR（異なる場合1）

#include <stdio.h>
int main() {
    int a = 10, b = 20;
    
    // XORによる値の交換（一時変数不要）
    a ^= b;
    b ^= a;
    a ^= b;
    
    printf("a=%d, b=%d\n", a, b); // a=20, b=10
    return 0;
}

注意：XOR交換は負数でも正しく動作します（補数表現の性質により）。ただし、同一アドレスの変数では失敗するため注意が必要です。

ビットカウントの実装例

整数の2進表現における1のビット数を数える方法：

// 方法1: 剰余と除算（負数に対応しない）
int count_bits_v1(int n) {
    int cnt = 0;
    while (n) {
        cnt += n % 2;
        n /= 2;
    }
    return cnt;
}

// 方法2: ビットマスク（32ビット固定）
int count_bits_v2(int n) {
    int cnt = 0;
    for (int i = 0; i < 32; i++) {
        if (n & (1U << i)) cnt++;
    }
    return cnt;
}

// 方法3: Brian Kernighanアルゴリズム（効率的）
int count_bits_v3(int n) {
    int cnt = 0;
    while (n) {
        n &= n - 1; // 最下位の1をクリア
        cnt++;
    }
    return cnt;
}

カンマ演算子

カンマで区切られた式は左から順に評価され、最後の式の値が全体の値になります：

int a = 1, b = 2, c;
c = (a += 2, b *= 3, a + b); // c = 9 (a=3, b=6)

制御フロー内でも使用可能ですが、可読性を損なうため多用は推奨されません。