More than one bit

[Crispy]

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 July 9, 2018 by Crispy

[Omegamatrix]

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

[ZackAttack]

8 cycles

 

LAX Input
DEX
SAX Output

 

[MLdB]

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

ADC input

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 July 5, 2018 by MLdB

[+SvOlli]

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.

[MLdB]

Zack's solution is awesome.

That made me curious

 

 

 

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)

 

 

[ZackAttack]

That made me curious

 

 

 

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.

[MLdB]

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 July 9, 2018 by MLdB

[MLdB]

And I second the motion for a weekly challenge

Edited July 7, 2018 by MLdB

[ZackAttack]

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.

[MLdB]

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

[Crispy]

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.

 

[vidak]

I vote for a challenge too!