กลับลำดับ 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	// สลับ 'บิตที่อยู่ตำแหน่งคี่' กับ 'บิตที่อยู่ตำแหน่งคู่'

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

2 คิดบน “กลับลำดับ Bit ในตัวแปร Integer

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s