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

Groups > comp.programming > #3127 > unrolled thread

bit twiddling hacks

Back to article view | Back to comp.programming

Contents

  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

#3127 — bit twiddling hacks

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.

[toc] | [next] | [standalone]

#3128

On Mon, 4 Mar 2013 15:09:54 -0800 (PST), bob <bob@coolfone.comze.com>
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);
>    }


Clever minds, long nights, excessive caffeine consumption...

As to that particular method for reversing a set of bits, it dates
back to *at least* the sixties.  And I would expect that it was known
almost since the dawn of modern computing.

[toc] | [prev] | [next] | [standalone]

#3129

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.

That's a classical recursive divide and conquer approach.
pseudo code for stuff above:

sequence rev(sequence a)
{
	if(single_bit(a))
		return a;
	split(a,&a1,&a2);
	a1=rev(a1);
	a2=rev(a2);
	return combine(a2,a1);
}

[toc] | [prev] | [next] | [standalone]

#3130

On Tuesday, March 5, 2013 2:52:08 AM UTC-6, Johann Klammer wrote:
> 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.
> 
> 
> 
> That's a classical recursive divide and conquer approach.
> 
> pseudo code for stuff above:
> 
> 
> 
> sequence rev(sequence a)
> 
> {
> 
> 	if(single_bit(a))
> 
> 		return a;
> 
> 	split(a,&a1,&a2);
> 
> 	a1=rev(a1);
> 
> 	a2=rev(a2);
> 
> 	return combine(a2,a1);
> 
> }

Thanks.

I guess it is not that useful to reverse bits or it would just be an instruction in most processors?

[toc] | [prev] | [next] | [standalone]

#3131

On 3/5/13 7:45 AM, bob wrote:
> On Tuesday, March 5, 2013 2:52:08 AM UTC-6, Johann Klammer wrote:
>> 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.
>>
>>
>>
>> That's a classical recursive divide and conquer approach.
>>
>> pseudo code for stuff above:
>>
>>
>>
>> sequence rev(sequence a)
>>
>> {
>>
>> 	if(single_bit(a))
>>
>> 		return a;
>>
>> 	split(a,&a1,&a2);
>>
>> 	a1=rev(a1);
>>
>> 	a2=rev(a2);
>>
>> 	return combine(a2,a1);
>>
>> }
>
> Thanks.
>
> I guess it is not that useful to reverse bits or it would just be an instruction in most processors?
>
Its not useful until you have use for it :-)

It is far less useful per-silicon needed to implement it than probably 
most instructions though, especially since it can be implemented via 
other instructions.

[toc] | [prev] | [next] | [standalone]

#3132

On Tue, 5 Mar 2013 07:45:40 -0800 (PST), bob <bob@coolfone.comze.com>
wrote:

>On Tuesday, March 5, 2013 2:52:08 AM UTC-6, Johann Klammer wrote:
>> 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.
>> 
>> 
>> 
>> That's a classical recursive divide and conquer approach.
>> 
>> pseudo code for stuff above:
>> 
>> 
>> 
>> sequence rev(sequence a)
>> 
>> {
>> 
>> 	if(single_bit(a))
>> 
>> 		return a;
>> 
>> 	split(a,&a1,&a2);
>> 
>> 	a1=rev(a1);
>> 
>> 	a2=rev(a2);
>> 
>> 	return combine(a2,a1);
>> 
>> }
>
>Thanks.
>
>I guess it is not that useful to reverse bits or it would just be an instruction in most processors?


Pretty much.  There are times when you need it, but not really that
often.  Hashes, cryptography and FFTs are notable places where it pops
up.

Many processors do have instructions to reverse the *byte* order in a
word (to handle big/little endian conversions).  You can use that
before or after swapping the bits around in the individual bytes (the
first three lines of the swap in your original code).

Hardware implementation always has tradeoffs for the benefit vs. the
cost.  Given that it's rarely used means the cost has to be small, but
unfortunately doing it in hardware requires a fair chunk of chip area
to handle all those wire crossings, although the "circuitry" is
obviously trivial.

[toc] | [prev] | [next] | [standalone]

#3133

Robert Wessel wrote:

> > I guess it is not that useful to reverse bits or it would just be an
> > instruction in most processors?
>
>
> Pretty much.  There are times when you need it, but not really that
> often.  Hashes, cryptography and FFTs are notable places where it pops
> up.

An additional point is that though those uses are important (I'm thinking 
especially of FFT), and are in fact important enough to get dedicated hardware 
support, the actual bit-reversal part is a minor factor in the overall cost, so 
accelerating that isn't the best way to use silicon.

    -- chris 

[toc] | [prev] | [next] | [standalone]

#3134

bob wrote:
> How do people typically come up with bit twiddling hacks like this?

Some folk have also used various kinds of automatic brute-force searches to
look for "clever" ways to implement particular operations within the
limitations of a given instruction set.

Searching for super-optimiser (exclude "tax" and "finance") will find examples.

    -- chris

[toc] | [prev] | [next] | [standalone]

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web