On Sunday, 24 April 2016 at 23:17:53 UTC, David Nadlinger wrote:
On Sunday, 24 April 2016 at 23:00:56 UTC, Temtaime wrote:
Please no cmp.
Just
bool isPowerOf2(uint x) { return x && !(x & (x - 1)); }
You do realise that this will (typically) emit a branch?
— David
I compiled using dmd -O and looked at the disassembly using
objdump -D and there are indeed a couple branches in the
disassembly:
0000000000000000 <_D4test8powerOf2FkZk>:
0: 50 push %rax
1: 48 89 f9 mov %rdi,%rcx
4: 85 c9 test %ecx,%ecx
6: 74 0a je 12
<_D4test8powerOf2FkZk+0x12>
8: 8d 81 ff ff ff ff lea -0x1(%rcx),%eax
e: 85 c1 test %eax,%ecx
10: 74 04 je 16
<_D4test8powerOf2FkZk+0x16>
12: 31 c0 xor %eax,%eax
14: eb 05 jmp 1b
<_D4test8powerOf2FkZk+0x1b>
16: b8 01 00 00 00 mov $0x1,%eax
1b: 59 pop %rcx
1c: c3 retq
1d: 0f 1f 00 nopl (%rax)
I modified David's solution a bit to (hopefully) eliminate the
branch:
bool powerOf2(uint x){ return !x ^ !(x & (x - 1)); }
0000000000000000 <_D4test8powerOf2FkZb>:
0: 50 push %rax
1: 53 push %rbx
2: 48 89 fa mov %rdi,%rdx
5: 85 d2 test %edx,%edx
7: 0f 94 c0 sete %al
a: 8d 8a ff ff ff ff lea -0x1(%rdx),%ecx
10: 85 ca test %ecx,%edx
12: 0f 94 c3 sete %bl
15: 32 c3 xor %bl,%al
17: 5b pop %rbx
18: 59 pop %rcx
19: c3 retq
1a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
The branches are gone but I'm really not sure if this is better
or worse.
