algorithm - Bit swapping O(logN)? -
i've been told reversing bits of integer in divide-and-conquer fashion (i.e. first swapping every 2 consecutive bits, swapping 2-bit pairs, , on until result) o(logn), fail see how o(logn)..
consider case when swapping byte (8 bit): first swap every 2 bits , perform 4 swaps, swap 2-bit pairs have 2 swaps , join in last swap. total: 7 swaps, log(n) have been 3.
am right or missing something?
you're counting else. if add "individual swaps", that's lot of swaps. whole point of technique (and many similar techniques) "phase", swaps in phase happen in constant number of steps. example step "swap adjacent bits":
x = ((x & 0x55) << 1) | ((x & 0xaa) >> 1);
.. or equivalent delta-swap formulation, looks no matter how many swaps it's doing (the constants change of course). so, that's constant number of steps right there. (cue complaining operations on n-bit integers not being single steps, here are, it's different way of counting)
it takes 3 delta-swaps (or simple swaps above) reverse byte.
Comments
Post a Comment