2006-04-23

A neat trick

Recently I was reading Knuth's The Art of Computer Programming (vol. 3). The "uniform binary search" algorithm uses ceil(x/2) operation where x is an integer. A very short, branch-free way occured to me how to code this operation. The following code assumes x in %eax and finishes with the desired result in %eax

shrl $1, %eax
adc $0, %eax


No comments: