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

Groups > comp.programming > #3130

Re: bit twiddling hacks

Show all headers | View raw

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?

Back to comp.programming | Previous | Next — Previous in thread | Next 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