Does anybody have a quick way to count the number of matching bits in two words?

youngdave · 2009-08-26 07:55

Dear All
Does anybody have a fast way to count the number of matching bits in two words?
eg
0101000010111101
1011100101010001
6 bits match in these two words.
TIA David Young

Timmoore · 2009-08-26 07:58

xor the 2 numbers and count the number of 0's

youngdave · 2009-08-26 08:10

Thanks.
Yes, I'm aware of the XOR, but I'm looking for a fast way to count the zeros.
TIA David Young

Nick Mueller · 2009-08-26 08:25

If you want it really fast, you could use a table. But that table will be a bit on the huge size.

But for 4 bits, the table is small enough.
The table would look like this:
%0000: 4
%0001: 3
%0010: 3
%0011: 2
%0100: 3
etc ...
shift and mask with %1111, look into the table with the result of the masking, add the 4 numbers of the table's result. You're done.

Or use a shifting mask, TEST and add if the compare is zero.

Nick

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Never use force, just go for a bigger hammer!

The DIY Digital-Readout for mills, lathes etc.:
YADRO

youngdave · 2009-08-26 08:42

Looks like a table's not the answer.

I'm really looking for something like the following:

word_XOR_result := word_value1 XOR word_value2
n := 1
repeat while n < 16
if word_XOR_result[noparse][[/noparse]bit#n] = 0
count++
n++

The bit I can't figure out is:
if word_XOR_result[noparse][[/noparse]bit#n] = 0

TIA David Young

SamMishal · 2009-08-26 08:46

Dave,

Here is a routine that would do what you ask.
Also find enclosed an archive that has a project that uses the method
to illustrate how it works....it uses the Parallax Terminal to enter numbers and output
the result....see the archive.

Pri CountZeros(number,bits)|c
   c~
   repeat bits
     if not (number & 1)
        c++
     number := number >> 1         
Return c

The method allows you to specify the number and the bits you want to count.
It will return the number of zeros within the bit count of the number.

See how the method is used in the demo program attached

Sam

SamMishal · 2009-08-26 08:55

Dave,

I just thought that you can make the method even more efficient this way

Pri CountZeros(number,bits)
   repeat bits
     if not (number & 1)
        Result++
     number >>= 1

By the way....this improvement relies on the fact that Result is the default return value
and that it will always be zeroed upon entry into the method.

I think this is true but just in case you can always add a Result~· just above the Repeat.

Regard

Samuel

Post Edited (SamMishal) : 8/26/2009 9:07:44 AM GMT

BradC · 2009-08-26 09:05

What about this ?

Pri CountZeros(number,bits)
  repeat bits
    Result += (number & 1)
    number >>=1
  result := bits-Result

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
lt's not particularly silly, is it?

youngdave · 2009-08-26 09:21

Will the following work?

VAR
word word_value

PUB testa | n, count

number := .................

count := 0
n := 0

repeat while n < 16
if not (word_value & 1)
count++
word_value >>= 1
n++

................. := count

TIA David Young

SamMishal · 2009-08-26 09:24

BradC said...
What about this ?

I like this idea·...but you can eliminate the Result:=bits-Result line if you do this

Pri CountZeros(number,bits)
   repeat bits
     Result += (number &1)^1
     number >>= 1

I think this is the most efficient .... I doubt you can get less code to do this.....

Sam

Post Edited (SamMishal) : 8/26/2009 9:32:11 AM GMT

SamMishal · 2009-08-26 09:34

youngdave said...
Will the following work?

Beware of indentation....Spin does not do what you think it would if you do not
indent to the correct level.....so your code as given will NOT work....you need to indent
stuff.

Also see what Brad and I have done....just use the METHOD we gave you....

Sam
·

BradC · 2009-08-26 09:40

SamMishal said...

BradC said...

What about this ?

I like this idea ...but you can eliminate the Result:=bits-Result line if you do this
Pri CountZeros(number,bits)
   repeat bits
     Result += (number &1)^1
     number >>= 1         
 
I think this is the most efficient .... I doubt you can get less code to do this.....

I'm not so sure it is. With my routine you only do one single subtraction at the end of the method. With your "optimisation" you add another constant and xor to each iteration of the loop.
For a loop of 16 bits, your's pushes an additional 14 constants and does an additional 15 math operations.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
lt's not particularly silly, is it?

SamMishal · 2009-08-26 09:46

Brad,

I agree with you when you put that way....

It just looks more elegant with just 3 lines of code...

Sam

youngdave · 2009-08-26 09:47

I've just tried the following, but it seems to hang up. Never mind, I'll get to that later.
Is it fundamentally sound?

PUB Fitness | n, nn, count

n := 1
repeat while n <> Current_Population_Size
nn := 0
repeat while nn <> 15
if not (Chromosome[noparse][[/noparse]n] & 1)
count++
Chromosome[noparse][[/noparse]n] >>= 1
nn++
n++

term.Str(String("Number of zero bits "))
term.dec(count)
term.CarriageReturn

TIA David Young

BradC · 2009-08-26 09:54

Dave, can you edit your code and put "[noparse][[/noparse]" code "]" tags around it so we can get a grasp on your indentation please?
Those code tags are left square bracket code right square bracket and ending with left square bracket /code right square bracket.

It looks ok at first glance but I'd like to see it properly indented.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
lt's not particularly silly, is it?

youngdave · 2009-08-26 10:17

Here it is with the proper layout.

[noparse][[/noparse]PUB Fitness | n, nn, count]

[noparse][[/noparse] n := 1]
[noparse][[/noparse] repeat while n <> Current_Population_Size]
[noparse][[/noparse] nn := 0]
[noparse][[/noparse] repeat while nn <> 15]
[noparse][[/noparse] if not (Chromosome[noparse][[/noparse]n] & 1)]
[noparse][[/noparse] count++]
[noparse][[/noparse] Chromosome[noparse][[/noparse]n] >>= 1]
[noparse][[/noparse] nn++]
[noparse][[/noparse] n++]

jazzed · 2009-08-26 10:28

Brad meant [noparse][[/noparse].code] your code [noparse][[/noparse]./code] without the dots '.'

Here is the same idea as before except written in PASM if you ever need it.

' pasm subroutine to count bits that are the same in t1 and t2
' count returned in t2
bitsame
  xor          t1,      t2
  mov          t2,      #0
  mov          t0,      #32
:loop
  shr          t1,      #1 wc
  if_nc add    t2,      #1
  djnz         t0,      #:loop
bitsame_ret ret

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
--Steve

Propeller Tools

Post Edited (jazzed) : 8/27/2009 3:39:07 AM GMT

SamMishal · 2009-08-27 03:27

Dave,

When you post code in the forum use the # button right above the Editor box while you are editing.

This gives you a box with blue text. You can paste your code in this box and it will show up
with the correct indentation etc.

Your code looks like it might be alright EXCEPT that I cannot tell for sure due to lack of indentation.
As I said before...SPIN CARES A LOT about the indentation

repeat while n < 16 
n++

is not the same as

repeat while n< 16 
    n++

So please repost your code with proper indentation within the box as you see above and then we can tell
if your code is right.

Also you are using

n:= 0 
repeat while n < 16 
   n++

this makes a loop of 16 times. There is a construct in SPIN that allows you to be more efficient. It is

Repeat 16

this construct works really well when you have a fixed number of times you need to loop. It avoids having to
use a counter variable and to increment it. Which are two savings.

Also for good programming and ease of changing things later·it is better to put things like 16 in a CONSTANT
in the CON section. This makes it easy for you to later make it a Byte (8) or Long (32) if you need to

Con 
   BitCount = 16 

Pub Main 
      repeat BitCount 
        'etc. etc.

So this way you can change the number 16 to 32 and the code will work for 32 bits instead.
In the example above it does not matter since you are using BitCount in only one place. But imagine if you
had BitCount in many places in the code. If you use 16 all over the place and need to change it to 32 later then
you have to change many places. With the constant BitCount all you have to do is change it in ONE place.

Regards

Sam

Post Edited (SamMishal) : 8/27/2009 3:32:54 AM GMT

Does anybody have a quick way to count the number of matching bits in two words?

Comments