Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3140

Re: bit twiddling hacks

Show all headers | View raw

bob wrote:

> How do people typically come up with bit twiddling hacks like this?
>
>     public static long reverse(long v) {
>         // Hacker's Delight 7-1, with minor tweak from Veldmeijer
>         // http://graphics.stanford.edu/~seander/bithacks.html
>         v = ((v >>> 1) & 0x5555555555555555L) | ((v & 0x5555555555555555L) << 1);
>         v = ((v >>> 2) & 0x3333333333333333L) | ((v & 0x3333333333333333L) << 2);
>         v = ((v >>> 4) & 0x0F0F0F0F0F0F0F0FL) | ((v & 0x0F0F0F0F0F0F0F0FL) << 4);
>         v = ((v >>> 8) & 0x00FF00FF00FF00FFL) | ((v & 0x00FF00FF00FF00FFL) << 8);
>         v = ((v >>>16) & 0x0000FFFF0000FFFFL) | ((v & 0x0000FFFF0000FFFFL) <<16);
>         return ((v >>>32)                   ) | ((v                      ) <<32);
>     }
>
> Thanks.

The algorithms come from a lot of sources. Some of the more interesting solutions
start out as simple idea or observation that then gets backed by careful analysis.
Others come from the recognizing useful patterns. Others take advantage of less
computationally intensive but good enough solutions to problems.

One of the more interesting ones I solved many years ago was a problem that was
published as, "If the following was solved for the general case then a whole class
of problems would be easy." The original author didn't say the problem was unlovable
but his comment was quoted and evolved into this unsolved problem . . ..

It turned out as soon as I looked it seriously it fell apart in less than half an hour.

w..

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

bit twiddling hacks bob <bob@coolfone.comze.com> - 2013-03-04 15:09 -0800
  Re: bit twiddling hacks Robert Wessel <robertwessel2@yahoo.com> - 2013-03-04 17:29 -0600
  Re: bit twiddling hacks Johann Klammer <klammerj@NOSPAM.a1.net> - 2013-03-05 09:52 +0100
    Re: bit twiddling hacks bob <bob@coolfone.comze.com> - 2013-03-05 07:45 -0800
      Re: bit twiddling hacks Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2013-03-05 09:18 -0800
      Re: bit twiddling hacks Robert Wessel <robertwessel2@yahoo.com> - 2013-03-05 12:48 -0600
        Re: bit twiddling hacks "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-03-06 07:54 +0000
  Re: bit twiddling hacks "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-03-06 07:58 +0000
  Re: bit twiddling hacks Walter Banks <walter@bytecraft.com> - 2013-03-06 16:19 -0500

csiph-web