Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail
From: Walter Banks <walter@bytecraft.com>
Newsgroups: comp.programming
Subject: Re: bit twiddling hacks
Date: Wed, 06 Mar 2013 16:19:21 -0500
Organization: Byte Craft Limited
Lines: 33
Message-ID: <5137B2D9.6F417E96@bytecraft.com>
References: <991e0977-0ea0-4e25-b71b-3c798f729614@googlegroups.com>
Reply-To: walter@bytecraft.com
NNTP-Posting-Host: bM4394rHhFh2VKcsrsg96Q.user.speranza.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Complaints-To: abuse@aioe.org
X-Mailer: Mozilla 4.79 [en]C-CCK-MCD NSCPCD479  (Windows NT 5.0; U)
X-Accept-Language: en
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com comp.programming:3140



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..