# More than one bit

## Recommended Posts

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:

```bool trigger(unsigned char b) {
return ((b & (b - 1)) != 0);
}```

Edited by Crispy

##### Share on other sites

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

8 cycles

LAX Input
DEX
SAX Output

##### Share on other sites

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

LDA input

SEC

SBC #1

BMI .Exit

TAY

EOR input

STA tmp

TYA

CMP tmp

.Exit:

; zero flag set = single bit set in punt

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

LDA input

SEC

SBC #1

BMI .Exit

AND input

.Exit

With unofficial opcodes: 11/12 cycles

LAX input

BNE .skip

DEX

.skip

DEX

SAX output

; Haven't looked at ZackAttack's solution, wondering how to get down to 8....

Edited by MLdB

##### Share on other sites

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.

loop0:
lsr
bcs loop1
bne loop0
loop1:
lsr
bcs end
bne loop1
end:

Zack's solution is awesome.

##### Share on other sites

Zack's solution is awesome.

I may be wrong, but I believe Zack's solution will return 'true' (meaning: single bit set) for input = 0 (no bits set). 0, when subtracting 1, behaves as if it was %100000000 (256)

##### Share on other sites

I may be wrong, but I believe Zack's solution will return 'true' (meaning: single bit set) for input = 0 (no bits set). 0, when subtracting 1, behaves as if it was %100000000 (256)

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

http://www.visual6502.org/JSSim/expert.html?a=0000&d=a0008480a780ca8780

(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.

##### Share on other sites

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

##### Share on other sites

And I second the motion for a weekly challenge

Edited by MLdB

##### Share on other sites

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.

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

I vote for a challenge too!

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.