นับ Leading Zeros และ Trailing Zeros ใน Binary Number ด้วย C

นับจำนวนศูนย์นำหน้า (Leading Zeros) และศูนย์ท้าย (Trailing Zeros) ในตัวแปร Integer โดยใช้ Bitwise Operations

Trailing Zeros (ศูนย์ท้าย)

จำนวนศูนย์ต่อเนื่องจาก LSB (Bit 0) จนเจอ '1' ตัวแรก

ตัวอย่าง: 24 = 0001 1000 (binary) → Trailing Zeros = 3

อัลกอริทึม

trail = 0;
for(i = 0; i < bit_width; i++) {
    if((n >> i) & 1) break;  // เจอ 1 ที่ bit i
    trail++;
}

Leading Zeros (ศูนย์นำหน้า)

จำนวนศูนย์ต่อเนื่องจาก MSB (Bit สูงสุด) จนเจอ '1' ตัวแรก

ตัวอย่าง: 94 (32-bit) = 0000...0001 011110 → Leading Zeros = 25

อัลกอริทึม

lead = 0;
msb = 1 << (bit_width - 1);  // 1000...0
for(i = 0; i < bit_width; i++) {
    if((n << i) & msb) break;  // เจอ 1 ที่ bit (msb - i)
    lead++;
}

ตัวอย่างโปรแกรมครบถ้วน

#include <stdio.h>
#include <stdint.h>
#include <limits.h>

// Count Trailing Zeros
int countTrailingZeros(uint32_t n) {
    if(n == 0) return 32;  // Special case
    int count = 0;
    while((n & 1) == 0) {
        n >>= 1;
        count++;
    }
    return count;
}

// Count Leading Zeros
int countLeadingZeros(uint32_t n) {
    if(n == 0) return 32;
    int count = 0;
    uint32_t msb = 1u << 31;
    while((n & msb) == 0) {
        n <<= 1;
        count++;
    }
    return count;
}

int main() {
    uint32_t num;
    
    printf("Enter number: ");
    scanf("%u", &num);
    
    printf("Binary: ");
    for(int i = 31; i >= 0; i--)
        printf("%d", (num >> i) & 1);
    printf("\n");
    
    printf("Trailing Zeros: %d\n", countTrailingZeros(num));
    printf("Leading Zeros: %d\n", countLeadingZeros(num));
    
    // Built-in functions (GCC/Clang)
    printf("__builtin_ctz: %d\n", __builtin_ctz(num));
    printf("__builtin_clz: %d\n", __builtin_clz(num));
    
    return 0;
}

ผลลัพธ์

Enter number: 24
Binary: 00000000000000000000000000011000
Trailing Zeros: 3
Leading Zeros: 27
__builtin_ctz: 3
__builtin_clz: 27

Enter number: 94
Binary: 00000000000000000000000001011110
Trailing Zeros: 1
Leading Zeros: 25
__builtin_ctz: 1
__builtin_clz: 25

Built-in Functions (Compiler Extensions)

การประยุกต์ใช้

• Memory Allocation (Buddy System - หา Power of 2)
• Bit Manipulation Tricks
• Compiler Optimizations
• Graphics (Texture Alignment)
• Networking (Subnet Mask Calculations)

คำเตือน

Behavior Undefined เมื่อ Input = 0 สำหรับ Built-in Functions ต้องเช็คก่อนใช้เสมอ