Jump to content

Photo

More than one bit


12 replies to this topic

#1 Crispy OFFLINE  

Crispy

    Star Raider

  • 65 posts

Posted Sun Jul 1, 2018 2:06 AM

While working on one of my FPGA designs, I came up with a trick that I thought was very cool. It turns out that I'm not the first one to think of it though, because when I googled it I found that it's already somewhat well known. I probably should have saved time by googling it in the first place, but where's the fun in that?

 

I was thinking that some of you might appreciate this trick as well, but instead of giving it away I'm going to pose it as a brain teaser. The problem that needs to be solved is this: you are receiving data from a producer that creates 8 bit values. You need to determine if there is more than one bit set in each byte that you receive. How would you do this?

 

For example, you receive a byte that contains the value 0x28. This byte has two bits set, so your program/logic will return a true condition to indicate that more than one bit is set in the byte. You can post your solution using C style syntax, or 6502 assembly, or actually anything that you like. There's no doubt that some of you already know this, so if you do then please wait a few days before giving it away. Also, no cheating and googling it before giving it a go yourself.

 

And the solution is:

Spoiler

 


Edited by Crispy, Sun Jul 8, 2018 11:14 PM.


#2 Omegamatrix OFFLINE  

Omegamatrix

    Quadrunner

  • 6,215 posts
  • Location:Canada

Posted Sun Jul 1, 2018 12:02 PM

Edit: Nevermind I thought you were asking if any bit was set.



#3 ZackAttack OFFLINE  

ZackAttack

    Dragonstomper

  • 748 posts
  • Location:Orlando, FL US

Posted Sun Jul 1, 2018 12:45 PM

8 cycles

Spoiler



#4 MLdB OFFLINE  

MLdB

    Star Raider

  • 71 posts
  • Location:Netherlands

Posted Mon Jul 2, 2018 1:32 AM

I don't think this is an optimal solution: 11/26 cycles, official opcodes only. Haven't tested it :D

Spoiler

 

I feel like a fool: 11/13 cycles, untested...

Spoiler

 

With unofficial opcodes: 11/12 cycles

Spoiler

Edited by MLdB, Wed Jul 4, 2018 6:53 PM.


#5 SvOlli OFFLINE  

SvOlli

    Chopper Commander

  • 214 posts
  • Location:Hannover, Germany

Posted Fri Jul 6, 2018 10:55 AM

Not very efficient, but will get the job done: on more than 1 bit set, the carry will be set, can be expanded for min 3 an so on.

Spoiler
Zack's solution is awesome.



#6 MLdB OFFLINE  

MLdB

    Star Raider

  • 71 posts
  • Location:Netherlands

Posted Fri Jul 6, 2018 3:57 PM

Zack's solution is awesome.


That made me curious :)

Spoiler


#7 ZackAttack OFFLINE  

ZackAttack

    Dragonstomper

  • 748 posts
  • Location:Orlando, FL US

Posted Fri Jul 6, 2018 6:34 PM

That made me curious :)

Spoiler

 

decrementing $00 will wrap around to $ff since it's an 8 bit register. You can verify this easily with visual 6502.

 

http://www.visual650...08480a780ca8780

 

(change the 00 after a0 in the url to test other values)

 

Don't give me too much credit. I was trying to figure out how to determine if a single bit was set and only when I went to post my original solution did I realize I solved the wrong problem. I think that actually made it easier to solve. Also, it doesn't update any status flags, so there may be a better solution if you want to branch instead of storing the value to ZP.

 

It would be cool if we had a new 6502 riddle to solve every week.



#8 MLdB OFFLINE  

MLdB

    Star Raider

  • 71 posts
  • Location:Netherlands

Posted Fri Jul 6, 2018 11:40 PM

What I meant was, you need to check for input value 0, as subtracting 1 results in 11111111, which can be viewed as 'wrapping around' or the result of subtracting 1 from 256, which does have a single bit set, albeit the imaginative (edit: "infinitive", pff autocorrect...) 9th. Therefore, in our solutions, it behaves the same as the other powers of 2 (single bits) and gives a false positive.


Edited by MLdB, Mon Jul 9, 2018 4:15 PM.


#9 MLdB OFFLINE  

MLdB

    Star Raider

  • 71 posts
  • Location:Netherlands

Posted Fri Jul 6, 2018 11:40 PM

And I second the motion for a weekly challenge :D

Edited by MLdB, Fri Jul 6, 2018 11:42 PM.


#10 ZackAttack OFFLINE  

ZackAttack

    Dragonstomper

  • 748 posts
  • Location:Orlando, FL US

Posted Sun Jul 8, 2018 6:51 PM

What I meant was, you need to check for input value 0, as subtracting 1 results in 11111111, which can be viewed as 'wrapping around' or the result of subtracting 1 from 256, which does have a single bit set, albeit the infinitive 9th. Therefore, in our solutions, it behaves the same as the other powers of 2 (single bits) and gives a false positive.

 

An input of 0 produces an output of 0. A is set to 0 and that 0 is ANDed with X to produce the result. So the value of X is irrelevant since anything ANDed with 0 will always be 0.

 

I'm having trouble understanding your comment about it being the same as the other powers of 2. The powers of 2 all have a single bit site, which is not more than one, and as a result the output is 0 for those as well.



#11 MLdB OFFLINE  

MLdB

    Star Raider

  • 71 posts
  • Location:Netherlands

Posted Sun Jul 8, 2018 10:30 PM

I'm sorry, you're right, I misread the assignment. I thought it said: if a single bit is set.

#12 Crispy OFFLINE  

Crispy

    Star Raider

  • Topic Starter
  • 65 posts

Posted Sun Jul 8, 2018 11:25 PM

It's been a week, so I posted the solution. Reading through the posts, I get the impression that I'm the only one here who didn't already know this trick. I was hoping to see more people jump in and share their ideas, but it still generated some good discussion. 

 

In addition, I also like the idea of a weekly 6502 assembly challenge. I'll put my brain to work, and try to come up with a couple.

 



#13 vidak OFFLINE  

vidak

    Moonsweeper

  • 458 posts
  • Location:Sydney, Australia

Posted Sun Jul 15, 2018 4:52 AM

I vote for a challenge too!




0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users