12.3 เลขฐานและตัวดำเนินการระดับบิต

คอมพิวเตอร์เก็บทุกอย่างเป็นเลขฐานสอง สีบนเว็บเขียนเป็นฐานสิบหกอย่าง #FF8800 และโจทย์แข่งขันชอบถามให้แปลงเลขระหว่างฐาน หน้านี้แปลงฐานสิบไปฐานใดๆ และแปลงกลับด้วยลูปที่ใช้ / กับ % ที่คุ้นเคย จากนั้นรู้จักตัวดำเนินการที่ทำงานกับ bit ทีละตัวโดยตรง ซึ่งใช้เก็บสถานะเปิดปิดหลายอย่างในตัวแปรเดียว และทำให้ยกกำลังแบบเร็วเขียนเป็นลูปสั้นๆ ได้

ค่าประจำหลัก

เลขฐานสิบ 2026 แปลว่า 2 × 1000 + 0 × 100 + 2 × 10 + 6 × 1 แต่ละหลักมีค่าเป็นสิบเท่าของหลักทางขวา และใช้เลขโดด 0 ถึง 9 เลขฐาน b ก็ทำแบบเดียวกัน แต่ละหลักมีค่าเป็น b เท่าของหลักทางขวา และใช้เลขโดด 0 ถึง b - 1

• ฐานสอง มีเลขโดดแค่ 0 กับ 1 ค่าประจำหลักจากขวาไปซ้ายคือ 1 2 4 8 16 ... 11111101010₂ = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2 = 2026
• ฐานแปด มีเลขโดด 0 ถึง 7 ค่าประจำหลักคือ 1 8 64 512 ... 3752₈ = 3 × 512 + 7 × 64 + 5 × 8 + 2 = 2026
• ฐานสิบหก ต้องมีเลขโดด 16 ตัว จึงใช้ A ถึง F แทน 10 ถึง 15 ค่าประจำหลักคือ 1 16 256 ... 7EA₁₆ = 7 × 256 + 14 × 16 + 10 = 2026

ฐานที่ใหญ่กว่า 16 ก็ใช้ตัวอักษรต่อไปเรื่อยๆ ฐาน 36 ใช้ 0 ถึง 9 และ A ถึง Z ครบพอดี

เลขโดดฐานสิบหกหนึ่งตัวแทนเลขฐานสองสี่หลักพอดี คนเขียนโปรแกรมจึงชอบเขียนฐานสองยาวๆ เป็นฐานสิบหกให้สั้นลง

แปลงฐานสิบเป็นฐาน b

n % b คือหลักขวาสุดของ n ในฐาน b และ n / b คือ n ที่ตัดหลักขวาสุดทิ้ง เหมือนที่ % 10 กับ / 10 ทำกับฐานสิบในหน้า 4.5 ทำซ้ำจน n เป็น 0 ก็ได้ครบทุกหลัก แปลง 2026 เป็นฐานสิบหก

หลักออกมาจากขวาไปซ้าย อ่านจากล่างขึ้นบนได้ 7EA จึงต้องเก็บหลักไว้ในอาเรย์ก่อน แล้วพิมพ์ย้อนกลับ

#include <stdio.h>

int main()
{
    char symbols[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // (1)!
    long long n;
    int base;
    scanf("%lld %d", &n, &base);
    char digits[70]; // (2)!
    int length = 0;
    do { // (3)!
        digits[length] = symbols[n % base];
        length++;
        n /= base;
    } while (n > 0);
    for (int i = length - 1; i >= 0; i--) {
        printf("%c", digits[i]);
    }
    printf("\n");
    return 0;
}

1. symbols[10] คือ 'A' symbols[35] คือ 'Z' ใช้เศษเป็น index แล้วได้เลขโดดทันที ไม่ต้องเขียน if แยกกรณี
2. เลขไม่เกิน 10¹⁸ ในฐานสองยาวไม่เกิน 60 หลัก ฐานอื่นสั้นกว่านั้น 70 ช่องจึงพอ
3. do while ทำให้เลข 0 ได้หลักเดียวคือ 0 แบบเดียวกับการนับหลักในหน้า 4.5

2026 2

11111101010

ป้อน 2026 16 ได้ 7EA ป้อน 2026 8 ได้ 3752 และป้อน 0 2 ได้ 0

แปลงฐาน b เป็นฐานสิบ

อ่านเลขเป็นข้อความทีละตัวจากซ้ายไปขวา ทุกครั้งที่ได้หลักใหม่ เลื่อนค่าเดิมไปทางซ้ายหนึ่งหลักด้วยการคูณ b แล้วบวกหลักใหม่ เป็นวิธีเดียวกับกลับเลขในหน้า 4.5 ที่คูณ 10 แล้วบวก ไล่ 7EA ฐานสิบหก

#include <stdio.h>

int main()
{
    char text[70];
    int base;
    scanf("%s %d", text, &base);
    long long value = 0;
    for (int i = 0; text[i] != '\0'; i++) {
        int digit;
        if (text[i] >= '0' && text[i] <= '9') {
            digit = text[i] - '0';
        } else {
            digit = text[i] - 'A' + 10;
        }
        value = value * base + digit;
    }
    printf("%lld\n", value);
    return 0;
}

7EA 16

2026

การแปลงตัวอักษรเป็นค่าใช้วิธีจากหน้า 6.1 ตัวเลขลบด้วย '0' ตัวอักษรลบด้วย 'A' แล้วบวก 10 ถ้าต้องแปลงจากฐาน a ไปฐาน b ที่ไม่ใช่ฐานสิบทั้งคู่ ให้แปลงเป็นค่าตัวเลขด้วยโปรแกรมนี้ก่อน แล้วส่งค่านั้นต่อให้โปรแกรม to_base

printf กับฐานแปดและฐานสิบหก

ฐานแปดและฐานสิบหกมีตัวกำหนดรูปแบบสำเร็จรูป ไม่ต้องเขียนลูปเอง

#include <stdio.h>

int main()
{
    int year = 2026;
    printf("%d %o %x %X\n", year, year, year, year);
    int color;
    scanf("%x", &color);
    printf("%d\n", color);
    return 0;
}

FF8800

2026 3752 7ea 7EA
16746496

• %o พิมพ์ฐานแปด %x พิมพ์ฐานสิบหกตัวพิมพ์เล็ก %X ตัวพิมพ์ใหญ่ ถ้าเป็น long long ใช้ %llx แบบเดียวกับ %lld
• scanf("%x", ...) รับเลขฐานสิบหกได้ทั้งตัวพิมพ์เล็กและใหญ่
• ฐานสองกับฐานอื่นนอกจากนี้ไม่มีตัวกำหนดรูปแบบในภาษา C ที่เราใช้ (C17) ต้องเขียนลูปเองแบบข้างบน

ตัวดำเนินการระดับบิต

ตัวดำเนินการกลุ่มนี้มองตัวเลขเป็นแถวของ bit แล้วทำงานทีละหลักของฐานสอง ใช้ a = 12 (1100₂) และ b = 10 (1010₂)

#include <stdio.h>

int main()
{
    int a = 12, b = 10;
    printf("a & b  = %d\n", a & b);
    printf("a | b  = %d\n", a | b);
    printf("a ^ b  = %d\n", a ^ b);
    printf("a << 1 = %d\n", a << 1);
    printf("a << 3 = %d\n", a << 3);
    printf("a >> 1 = %d\n", a >> 1);
    printf("a >> 2 = %d\n", a >> 2);
    return 0;
}

a & b  = 8
a | b  = 14
a ^ b  = 6
a << 1 = 24
a << 3 = 96
a >> 1 = 6
a >> 2 = 3

เลื่อนซ้าย k หลักคือคูณ 2^k เหมือนเติม 0 ท้ายเลขฐานสิบคือคูณ 10 ส่วนเลื่อนขวา k หลักคือหาร 2^k แบบตัดเศษ (สำหรับเลขที่ไม่ติดลบ) อย่าสับสน & กับ && ในบทที่ 3 && ตอบแค่จริงหรือเท็จ ส่วน & ทำทุก bit แล้วได้ตัวเลขใหม่ และ ^ ในภาษา C ไม่ใช่ยกกำลัง

ใช้ bit เป็นสวิตช์

ห้องเรียนมีไฟ 8 ดวง หมายเลข 0 ถึง 7 เก็บสถานะทั้งหมดในตัวเลขตัวเดียว bit ที่ k เป็น 1 แปลว่าไฟดวงที่ k เปิดอยู่ เช่น 37 = 100101₂ คือดวงที่ 0 2 และ 5 เปิด

#include <stdio.h>

int main()
{
    int state;
    scanf("%d", &state);
    int on = 0;
    for (int k = 0; k < 8; k++) {
        if ((state >> k) & 1) {
            printf("lamp %d is on\n", k);
            on++;
        }
    }
    printf("total on = %d\n", on);
    state = state | (1 << 6);
    printf("after turning on lamp 6 = %d\n", state);
    state = state ^ (1 << 0);
    printf("after flipping lamp 0 = %d\n", state);
    return 0;
}

37

lamp 0 is on
lamp 2 is on
lamp 5 is on
total on = 3
after turning on lamp 6 = 101
after flipping lamp 0 = 100

XOR มีสมบัติที่ใช้บ่อยในโจทย์ x ^ x ได้ 0 เสมอ x ^ 0 ได้ x และสลับลำดับได้ เช่น 5 ^ 3 ^ 5 เท่ากับ 5 ^ 5 ^ 3 ซึ่งก็คือ 0 ^ 3 ได้ 3 พูดง่ายๆ คือเลขที่ XOR เข้าไปสองครั้งจะหักล้างกันหายไป

ยกกำลังแบบเร็วด้วยลูป

ยกกำลังแบบเร็วในหน้า 12.1 เขียนเป็นลูปได้ ถ้ามองเลขชี้กำลังเป็นฐานสอง เช่น 13 = 1101₂ = 8 + 4 + 1 จึงได้ 3¹³ = 3⁸ × 3⁴ × 3¹ ไล่ bit ของ 13 จากขวาไปซ้าย พร้อมกับยกกำลังสองฐานไปเรื่อยๆ ให้ได้ 3¹ 3² 3⁴ 3⁸ bit ไหนเป็น 1 ก็คูณค่านั้นเข้าคำตอบ

#include <stdio.h>
#define MOD 1000000007

int main()
{
    long long base, exp;
    scanf("%lld %lld", &base, &exp);
    base %= MOD;
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) {
            result = result * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }
    printf("%lld\n", result);
    return 0;
}

3 13

1594323

exp >>= 1 คือ exp = exp >> 1 ตัดหลักขวาสุดของฐานสองทิ้ง เหมือน exp /= 2 ลูปวนเท่ากับจำนวนหลักฐานสองของ exp ซึ่งสำหรับ 10¹⁸ คือ 60 รอบ ได้ผลเท่ากับแบบ recursion ทุกค่า เลือกเขียนแบบที่ตัวเองจำได้แม่นกว่า

ลองทำให้พัง

แบบที่ 1 ไม่ใส่วงเล็บรอบ &

if (x & 1 == 0) {
    printf("even\n");
} else {
    printf("odd\n");
}

even.c:7:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
    7 |     if (x & 1 == 0) {
      |           ^

ป้อน 4 ได้ odd == มีลำดับสูงกว่า & โปรแกรมจึงทำ 1 == 0 ได้ 0 ก่อน แล้ว x & 0 ได้ 0 เสมอ ทุกเลขจึงตกไปที่ else compiler เตือนให้ใส่วงเล็บ ทำตามนั้นเป็น (x & 1) == 0 ใช้ & | ^ ร่วมกับตัวดำเนินการอื่นเมื่อไร ใส่วงเล็บทุกครั้ง

แบบที่ 2 เลื่อน 1 เกินขนาดของ int

long long big = 1 << 40;

shift.c:5:23: warning: left shift count >= width of type [-Wshift-count-overflow]
    5 |     long long big = 1 << 40;
      |                       ^~

เลข 1 เป็น int มีแค่ 32 bit เลื่อนไป 40 หลักก็หลุดออกนอกกล่อง บนเครื่องที่เขียนเอกสารนี้พิมพ์ออกมาเป็น 0 กับดักเดียวกับ int คูณ int ในหน้า 1.3 คือชนิดของผลมาจากตัวที่คำนวณ ไม่ใช่กล่องที่รับ แก้เป็น 1LL << 40 ซึ่งเป็น long long ตั้งแต่ต้น

แบบที่ 3 ป้อนเลขฐานสิบหกเป็นตัวพิมพ์เล็ก

ป้อน 7ea 16 ให้โปรแกรม from_base

7ea 16

2570

ได้ 2570 แทน 2026 'e' - 'A' + 10 ได้ 46 ไม่ใช่ 14 เพราะตัวพิมพ์เล็กมีรหัส ASCII ห่างจากตัวพิมพ์ใหญ่ 32 โปรแกรมไม่รู้ตัวว่าได้เลขโดดที่เกินฐาน คำนวณต่อไปเฉยๆ ถ้าโจทย์ไม่ได้รับประกันว่าเป็นตัวพิมพ์ใหญ่ ให้เพิ่มกรณี text[i] >= 'a' && text[i] <= 'z' ที่ลบด้วย 'a' แทน อ่านโจทย์ให้ชัดว่าตัวอักษรในข้อมูลเข้าเป็นแบบไหน

สรุป

• เลขฐาน b แต่ละหลักมีค่าเป็น b เท่าของหลักทางขวา ใช้เลขโดด 0 ถึง b - 1 เกิน 9 ใช้ A B C ...
• ฐานสิบไปฐาน b ใช้ % b กับ / b ซ้ำ เก็บหลักไว้แล้วพิมพ์ย้อนกลับ ฐาน b ไปฐานสิบใช้ value * b + digit
• %o %x %X พิมพ์ฐานแปดและสิบหก ฐานสองต้องเขียนเอง
• & | ^ ทำทีละ bit << k คูณ 2^k >> k หาร 2^k ใส่วงเล็บทุกครั้งที่ใช้คู่กับตัวดำเนินการอื่น และใช้ 1LL เมื่อเลื่อนตั้งแต่ 31 หลักขึ้นไป
• ยกกำลังแบบเร็วเขียนเป็นลูปได้ ด้วยการไล่ bit ของเลขชี้กำลัง