# More than one bit

12 replies to this topic

### #1 CrispyOFFLINE

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 OmegamatrixOFFLINE

Omegamatrix

• 6,233 posts

Posted Sun Jul 1, 2018 12:02 PM

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

### #3 ZackAttackOFFLINE

ZackAttack

Dragonstomper

• 761 posts
• Location:Orlando, FL US

Posted Sun Jul 1, 2018 12:45 PM

8 cycles

Spoiler

### #4 MLdBOFFLINE

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

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 SvOlliOFFLINE

SvOlli

Chopper Commander

• 215 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 MLdBOFFLINE

MLdB

Star Raider

• 71 posts
• Location:Netherlands

Posted Fri Jul 6, 2018 3:57 PM

Zack's solution is awesome.

Spoiler

### #7 ZackAttackOFFLINE

ZackAttack

Dragonstomper

• 761 posts
• Location:Orlando, FL US

Posted Fri Jul 6, 2018 6:34 PM

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 MLdBOFFLINE

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 MLdBOFFLINE

MLdB

Star Raider

• 71 posts
• Location:Netherlands

Posted Fri Jul 6, 2018 11:40 PM

And I second the motion for a weekly challenge

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

### #10 ZackAttackOFFLINE

ZackAttack

Dragonstomper

• 761 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 MLdBOFFLINE

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 CrispyOFFLINE

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 vidakOFFLINE

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