Jump to content
Crispy

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
  • Like 2

Share this post


Link to post
Share on other sites

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

 

 

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 by MLdB

Share this post


Link to post
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 this post


Link to post
Share on other sites

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)

 

 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
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 this post


Link to post
Share on other sites

And I second the motion for a weekly challenge :D

Edited by MLdB

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

 

  • Like 1

Share this post


Link to post
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...