ตรวจ 2^n

วันก่อนเห็นทวีตนี้ของ @Methuz

Best way to check if number is a power of two return ((x != 0) && ((x & (~x + 1)) == x))

— Midas~♫ (@Methuz) June 24, 2015

แล้วก็มานึกได้ว่าเคยเห็นโจทย์นี้มานานแล้วนะ พอนั่งคิดต่ออีกหน่อยก็พบว่าปรับปรุงให้ดีขึ้นได้อีก โดยเปลี่ยนส่วนที่กลับข้างบิตแล้วเปรียบเทียบกับตัวเอง ไปเป็นไม่ต้องกลับข้างบิตแต่เอาไปเทียบกับศูนย์แทน กล่าวคือ

@Methuz ((x != 0) && ((x & (x - 1)) == 0))

— เนยสดร้องไห้ทำมัย (@neizod) June 24, 2015

---

ถ้าไม่เชี่ยววิเคราะห์อัลกอริทึม ดูแค่นี้อาจยังมองไม่เห็นว่าปรับปรุงดีขึ้นจริงหรือเปล่า เลย compile เป็น assembly ออกมาแล้วไล่ดูทีละบรรทัดเลย

คำสั่งที่ใช้ compile ให้เป็น assembly (GAS syntax) คือ

$ gcc -S -O3 program.c

อันนี้คือผลลัพธ์แบบแรกที่คุณ @Methuz เสนอ (ตัดมาเฉพาะส่วนฟังก์ชันที่สำคัญนะครับ)

chkpowof2:
        xorl    %eax, %eax
        testl   %edi, %edi
        je      .L42
        movl    %edi, %eax
        negl    %eax
        andl    %edi, %eax
        cmpl    %eax, %edi
        sete    %al
        movzbl  %al, %eax
.L42:
        rep ret

และอันนี้เป็นแบบที่ปรับปรุงแล้ว

chkpowof2:
        xorl    %eax, %eax
        testl   %edi, %edi
        je      .L42
        leal    -1(%rdi), %eax
        testl   %edi, %eax
        sete    %al
        movzbl  %al, %eax
.L42:
        rep ret

โอเค ใครอ่านถึงตรงนี้แล้วไม่งงก็กดปิดได้ เพราะเห็นชัดว่าปรับปรุงให้ดีขึ้นจริง

ส่วนใครงงอยู่ เดี๋ยวมาไล่โค้ดกันทีละบรรทัดกันครับ :D

---

แต่ก่อนอื่น หากอยากอ่าน assembly รู้เรื่อง ก็ต้องไปทำความคุ้นเคยกับ register เสียก่อน (พวกที่เขียนด้วยเครื่องหมาย % นำหน้า) ซึ่งมันก็คือตัวแปรต่างๆ นั่นเอง เพียงแต่ว่าตำแหน่งในโลกจริงของ register ถูกวางไว้ใน CPU เพื่อให้ทำงานได้อย่างรวดเร็ว ทำให้ register ทั้งหมดนั้นมีอยู่อย่างจำกัด (ไม่กี่สิบตัว)

ในฟังก์ชันที่ตัดมานี้มี register ที่สำคัญอยู่ 2 ตัว คือ %eax และ %edi และยังมี register ตัวอื่นอีก เช่น %al ซึ่งเป็นส่วนย่อยของ %eax โดยอธิบายความสัมพันธ์ได้ดังแผนภาพนี้

sample value:
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

a family register:
                                                            |- %ah -| |- %al -|
                                                            |------ %ax ------|
                                        |--------------- %eax ----------------|
|----------------------------------- %rax ------------------------------------|

di family register:
                                                            |------ %di ------|
                                        |--------------- %edi ----------------|
|----------------------------------- %rdi ------------------------------------|

ดังนั้นหากค่าของ %eax (32 บิต) ถูกตั้งไว้เป็น 0x89ABCDEF เมื่อเรียกดูค่าของ %al (8 บิต) ก็จะว่ามีค่าเป็น 0xEF

ส่วนหน้าที่พิเศษของ register ทั้ง 2 ตัวในที่นี้คือ

• %eax เก็บค่าที่จะ return จากฟังก์ชัน
• %edi เก็บค่า argument ของฟังก์ชัน

พอคุ้นเคยกับ register เหล่านี้แล้ว คราวนี้ก็ได้เวลามาดูโค้ดจริงๆ เสียที

บรรทัด 1

xorl    %eax, %eax

บรรทัดแรกนี้สั่งล้างค่า %eax ให้เป็นศูนย์ไว้ก่อน โดยใช้เทคนิคว่า ค่าใดๆ เมื่อนำไป xor กับตัวเองแล้วจะได้ศูนย์เสมอ ท่านี้จะเร็วกว่าการโหลดข้อมูลจาก memory มาถม

บรรทัด 2-3:

testl   %edi, %edi
je      .L42

สองบรรทัดต่อมาเป็นการเช็คว่า %edi (ตัวแปร x) มีค่าเป็นศูนย์หรือเปล่า โดยใช้เทคนิคว่า ค่าใดๆ เมื่อนำไป and กับตัวเองก็จะได้ตัวเองเสมอ หากตรวจแล้วพบว่าเป็นศูนย์ก็ให้กระโดดไปยังจุดจบฟังก์ชัน ซึ่งเมื่อรวมกับข้อมูลก่อนหน้าว่าตอนนี้ %eax เป็นศูนย์อยู่ ก็คือฟังก์ชันนี้ให้คำตอบเป็น false นั่นเอง

บรรทัด 4-8 ของแบบแรก:

movl    %edi, %eax
negl    %eax
andl    %edi, %eax
cmpl    %eax, %edi
sete    %al

บรรทัดต่อๆ มาเป็นชุดคำสั่งในส่วนหลังที่ถามว่า หากมอง x เป็น binary แล้ว จะมีตัวเลข 1 เพียงตัวเดียวเท่านั้นหรือเปล่า? ซึ่งโค้ดชุดนี้ทำงานโดยเริ่มจากการคัดลอกค่า x จาก %edi มาไว้ที่ %eax ก่อน แล้วหาค่าติดลบแบบ two complement ของ %eax และเก็บไว้ที่เดิม (มีค่าเทียบได้กับการคำนวณ ~x+1) แล้วจึงเอาค่าของ %edi ไปทำการ and และเก็บค่าไว้ใน %eax (ตอนนี้ %eax ก็จะเก็บค่าของ x&(~x+1) แล้ว) สุดท้ายถามว่า %eax ลบ %edi ได้ศูนย์หรือเปล่า ถ้าใช่ก็จะตั้งค่า %al ให้เท่ากับหนึ่ง (ซึ่งก็คือ ฟังก์ชันจะคืนค่า true)

บรรทัด 4-6 ของแบบสอง:

leal    -1(%rdi), %eax
testl   %edi, %eax
sete    %al

ชุดบรรทัดพวกนี้มีหน้าที่และผลลัพธ์เหมือนกับชุดบรรทัดในหัวข้อย่อยก่อนเลยครับ สิ่งที่แตกต่างคือวิธีการเท่านั้น โดยโค้ดเริ่มทำงานจากคัดลอกค่า x จาก %rdi มาลบหนึ่งระหว่างทางแล้วเอาผลลัพธ์ไปเก็บไว้ใน %eax (ตรงนี้เนื่องจากมีการคำนวณพื้นฐานอย่างบวกลบ ทำให้ compiler รวบคำสั่งเข้ามาที่เดียว ต่างจากการคำนวณซับซ้อนอย่างการหาค่าติดลบครับ) เรียบร้อยแล้วเอา %edi มา and กับ %eax หากได้ศูนย์ก็จะตั้งค่า %al ให้เท่ากับหนึ่ง (คืน true)

บรรทัดรองสุดท้าย

movzbl  %al, %eax

ถึงตอนนี้การคำนวณหลักๆ ได้เสร็จสิ้นหมดแล้ว ที่ยังไม่เสร็จคือเตรียมค่าที่จะส่งคืน เพราะก่อนหน้านี้เราใช้ %al ยาว 8 บิต แต่ตอนส่งค่าคืนต้องใช้ %eax ที่ยาว 32 บิต บรรทัดนี้จะช่วยแปลงค่าดังกล่าว

บรรทัดสุดท้าย

rep ret

สุดท้ายก็ได้เวลาส่งคืนคำตอบครับ สังเกตว่า compiler เพิ่มความมั่นใจให้คำสั่งนี้ด้วยการเติม rep ไว้ข้างหน้า เพื่อให้โค้ดที่ทำงานมาถึงบรรทัดนี้ทำคำสั่ง ret ซ้ำๆ จนกว่าจะสำเร็จนั่นเอง

---

สุดท้ายการวิเคราะห์อัลกอริทึม/โค้ดยังไม่พอ นี่คือผลเชิงประจักษ์ของเวลาที่ใช้ไปสำหรับการตรวจว่าเลขดังกล่าวเป็น 2^n หรือไม่ สำหรับจำนวนเต็มบวกทุกตัวที่มีค่าต่ำกว่าสองพันล้านครับ

$ gcc --version
gcc (Ubuntu 4.9.2-10ubuntu13) 4.9.2
$ cat /proc/cpuinfo
...
model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
...


$ time method-1         # ((x != 0) && ((x & (~x + 1)) == x))
real 0m0.234s ~ 0m0.289s
user 0m0.232s ~ 0m0.288s
sys 0m0.000s


$ time method-2         # ((x != 0) && ((x & (x - 1)) == 0))
real 0m0.212s ~ 0m0.262s
user 0m0.208s ~ 0m0.260s
sys 0m0.000s

ก็เร็วต่างกันประมาณ 10%