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

Groups > comp.programming > #1123

Re: n bits on of m bits

Cross-posted to 3 groups.

Show all headers | View raw

In sci.math Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
> On 12/19/11 2:44 PM, kym@kymhorsell.com wrote:
>> In sci.math The Last Danish Pastry<clivet@gmail.com>  wrote:
>> ....
>>>   public static int CountBinaryOnes(long x)
>>>   {
>>>     int result = 0;
>>>
>>>     while (x>  0)
>>>     {
>>>       ++result;
>>>       x&= x-1;
>>
>> The traditional method on 2s compl machinery is
>>       x&= -x;
> I've seen cleverer ways that are O(logn) best/worse case.

Yes, these bit shifting/masking methods became popular when big shifters
became cheap and looping caused bubbles in the pipeline.

E.g.
	y = (x&0x55555555)+((x>>1)&0x55555555)

will convert  a vector of bit quantities "x[i]" to a vector of 2-bit 
quanitites "y[j]" where y[j] = x[2*j]+x[2*j+1]

Then
	z = (y&0x33333333)+((y>>2)&0x33333333)

willconvert a vector of 2-bit quantities y[i] into  a vector of 4-bit
quantities z[j] such that z[j] = y[2*j]+y[2*j+1]

Etc, until all the bits in the wordsize have been added. Or maybe cheat with
some MMX instructions. :)

Which of the shift/mask or "count number of 1's using 2s compl" is actually
the fastest for a given architecture usually devolves to measurement
after appropriately weighting the expected arguments.

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

Thread

n bits on of m bits Andrew Tomazos <andrew@tomazos.com> - 2011-12-17 08:05 -0800
  Re: n bits on of m bits Robert Wessel <robertwessel2@yahoo.com> - 2011-12-17 10:44 -0600
  Re: n bits on of m bits Dave <dave_and_darla@Juno.com> - 2011-12-17 08:56 -0800
  Re: n bits on of m bits richard@cogsci.ed.ac.uk (Richard Tobin) - 2011-12-17 17:22 +0000
  Re: n bits on of m bits "BartC" <bc@freeuk.com> - 2011-12-17 18:23 +0000
    Re: n bits on of m bits Andrew Tomazos <andrew@tomazos.com> - 2011-12-17 11:05 -0800
  Re: n bits on of m bits Robert Wessel <robertwessel2@yahoo.com> - 2011-12-17 13:24 -0600
    Re: n bits on of m bits Robert Wessel <robertwessel2@yahoo.com> - 2011-12-17 13:47 -0600
  Re: n bits on of m bits blp@cs.stanford.edu (Ben Pfaff) - 2011-12-17 11:28 -0800
  Re: n bits on of m bits "The Last Danish Pastry" <clivet@gmail.com> - 2011-12-19 21:52 +0000
    Re: n bits on of m bits kym@kymhorsell.com - 2011-12-19 22:44 +0000
      Re: n bits on of m bits Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-19 15:33 -0800
        Re: n bits on of m bits kym@kymhorsell.com - 2011-12-20 03:51 +0000
        Re: n bits on of m bits Willem <willem@toad.stack.nl> - 2011-12-20 10:05 +0000
          Re: n bits on of m bits Patricia Shanahan <pats@acm.org> - 2011-12-20 07:16 -0800
            Re: n bits on of m bits Dave <dave_and_darla@Juno.com> - 2011-12-20 07:29 -0800
              Re: n bits on of m bits Willem <willem@toad.stack.nl> - 2011-12-20 16:00 +0000
      Re: n bits on of m bits The Last Danish Pastry <clivet@gmail.com> - 2011-12-19 16:41 -0800
        Re: n bits on of m bits kym@kymhorsell.com - 2011-12-20 04:29 +0000
  Re: n bits on of m bits kym@kymhorsell.com - 2011-12-20 19:04 +0000
  Re: n bits on of m bits Robin Vowels <robin.vowels@gmail.com> - 2011-12-22 07:25 -0800
    Re: n bits on of m bits Willem <willem@toad.stack.nl> - 2011-12-22 15:58 +0000
      Re: n bits on of m bits Robin Vowels <robin.vowels@gmail.com> - 2011-12-22 16:26 -0800
        Re: n bits on of m bits Willem <willem@toad.stack.nl> - 2011-12-23 18:58 +0000
          Re: n bits on of m bits Robin Vowels <robin.vowels@gmail.com> - 2011-12-25 04:01 -0800
            Re: n bits on of m bits Dave <dave_and_darla@Juno.com> - 2011-12-25 09:22 -0800
  Re: n bits on of m bits Dr J R Stockton <reply1151@merlyn.demon.co.uk> - 2011-12-24 23:36 +0000
  Re: n bits on of m bits "io_x" <a@b.c.invalid> - 2011-12-31 16:32 +0100

csiph-web