I need a routine to isolate the high bit of a byte.
so eg 80-FF should return 80, 40-7F should return 40, etc

Even 32 bytes for nibble wise LUTs seems excessive,
but I wouldn't rule it out if it there was enough of a
speed advantage.

this is the best I've come up with


Any better ideas?

Warren's "Hacker's Delight" suggests
which would be
I haven't fully tested this.

I thought I might find something in HAKMEM but no.

Cheers
Ed

Edit: oops, that only makes a mask. To reduce to top bit set we must also do

How about:

or the same thing, non-structured:

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Nice work, Bogax. It's a delightfully tidy algorithm -- not to be improved upon! (at least not by me).

The implementation can be tightened up a bit, though. A few of the instructions are eligible for substitution on a one-for-one basis, as follows:Using lda as a substitute for eor may seem odd but it's acceptable simply because A is known to be zero, owing to the immediately preceding bne instruction. (The substitution improves readability, IMO. But that's not the primary benefit.)

Now the value temp has nothing happening to it except simple move operations. It becomes feasible to keep the value in a register rather than a zero-page location (see below). This saves 4 bytes and up to 4 cycles.

And I haven't fully wrapped my brain around this! Good one, Ed! But I won't be able to give it full concentration until tomorrow. It's past bedtime on this side of the pond, and I'm sleepy (whereas I'm guessing you just got up!)

cheers

Jeff

_________________
In 1988 my 65C02 got six new registers and 44 new full-speed instructions!
https://laughtonelectronics.com/Arcana/ ... mmary.html

Agreed, Bogax' code is very nice - and mine was wrong (is now updated)

Resurrecting an old thread, because it's the only mention of Hacker's Delight I could find. And I wanted to add a link to a related site, called Bit Twiddling, as recently noted over at the HP Museum:
https://graphics.stanford.edu/~seander/bithacks.html
via
http://www.hpmuseum.org/forum/thread-49 ... 44284.html
which mentions some other books which might be of interest.

In addition to Dr Jefyll's saving with using TAY and TYA, you can shave 1 cycle off worse case execution in the first part of the routine.

Change this:


To this:

How about removing rightmost bits until you reach the last. NUM must be non-zero at the start and will contain the last bit at the end.

Utterly untested

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

I see no requirement for NUM being non-zero here. If NUM is zero on entry, it will also be so on exit.

Agreed. I was playing safe.

Slightly smaller if you shuffle the instructions and put the initial value in A. Result still in NUM.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

Nice, if memory economy is the goal. Of course the other potential priority is speed, which, judging from the lead post, is what Bogax was interested in. His algorithm has a very fast worst-case execution because there's no looping.

Good spot, Omegamatrix -- I missed that! The 2nd instruction tests the high 4 bits, but the test needn't be destructive as in my previous version. CMP and BIT are both capable of doing the test while at the same time preserving the contents of A. I've adopted your suggestion (below) but I prefer to use BIT since it's just as fast as CMP and IMO is slightly more readable.



-- Jeff

_________________
In 1988 my 65C02 got six new registers and 44 new full-speed instructions!
https://laughtonelectronics.com/Arcana/ ... mmary.html

I have only programmed for the 6502, and there's no BIT #IMM instruction for it. Looking at the 65C02 and 65816 I see there is.