วันก่อนเห็นทวีตนี้ของ
@Methuz
แล้วก็มานึกได้ว่าเคยเห็นโจทย์นี้มานานแล้วนะ พอนั่งคิดต่ออีกหน่อยก็พบว่าปรับปรุงให้ดีขึ้นได้อีก โดยเปลี่ยนส่วนที่กลับข้างบิตแล้วเปรียบเทียบกับตัวเอง ไปเป็นไม่ต้องกลับข้างบิตแต่เอาไปเทียบกับศูนย์แทน กล่าวคือ
ถ้าไม่เชี่ยววิเคราะห์อัลกอริทึม ดูแค่นี้อาจยังมองไม่เห็นว่าปรับปรุงดีขึ้นจริงหรือเปล่า เลย 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%
