กลับลำดับ Bit ในตัวแปร Integer

วันนี้เขียน Micro C ลง dsPIC30 (เป็น Microcontroller ตัวนึงน่ะนะ) ต้องการเขียนโปรแกรมให้กลับลำดับ bit ในตัวแปร x

x = 01001111000000001010101011110000

ให้กลายเป็น

y = 00001111010101010000000011110010

(คือ เขียน bit ใน x จากหลังมาหน้านั่นแหละครับ)

ตอนแรกพยายามนึกวิธีเอง ได้วิธีถึกๆ แบบต้องวนลูป 32 ครั้งค่อยๆ ดึง bit ตัวท้ายออกมาใส่อีกตัวแปรนึงไปเรื่อยๆ (32 ครั้ง = 32 bit) พอไปค้นในเน็ตเจอ Bit Twiddling Hacks ซึ่งแข็งแกร่งมาก (ทำเสร็จในไม่กี่ operation) ขอเอาโค้ดมาแปะตามนี้

unsigned int v; // 32 bit word to reverse bit order
// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) <> 2) & 0x33333333) | ((v & 0x33333333) <> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) <> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) <> 16             ) | ( v               << 16);

ตอนแรกดูโค้ดแล้วก็งงๆ มันทำงานได้ยังไงหว่า ขอยกตัวอย่างการทำงานกับเลข 8 bit โดยใช้สัญลักษณ์ ABCDEFGH แทน 0, 1 และขอรันโค้ดจากบรรทัดล่างขึ้นบนซึ่งให้ผลลัพธ์เหมือนกัน (มันจะเข้าใจง่ายกว่าจริงๆ นะ)

x = ABCDEFGH
x = EFGHABCD	// สลับ nibble (4 bits) ที่ติดกัน
x = GHEFCDAB	// สลับ คู่บิต (2 bits) ที่ติดกัน
x = HGFEDCBA	// สลับ 'บิตที่อยู่ตำแหน่งคี่' กับ 'บิตที่อยู่ตำแหน่งคู่'

ถ้ายังไม่เข้าใจบ่นได้เลยครับ 😀