6502.org • isolate the high bit of a byte

Page 1 of 1

isolate the high bit of a byte

Posted: Tue Jul 31, 2012 4:34 am

by bogax

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

Code: Select all

HIBIT
 lda num
 and #$F0
 bne SKIP1
 eor num
SKIP1
 sta temp
 and #$CC
 bne SKIP2
 eor temp
SKIP2
 sta temp
 and #$AA
 bne SKIP3
 eor temp
SKIP3
 rts

Any better ideas?

Re: isolate the high bit of a byte

Posted: Tue Jul 31, 2012 5:57 am

by BigEd

Warren's "Hacker's Delight" suggests

Code: Select all

x=x | (x >> 1)
x=x | (x >> 2)
x=x | (x >> 4)

which would be

Code: Select all

HIBIT
 lda num
 lsr 
 ora num
 sta num
 lsr 
 lsr 
 ora num
 sta num
 lsr
 lsr 
 lsr 
 lsr 
 ora num

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

Code: Select all

sec
adc #0
ror

Re: isolate the high bit of a byte

Posted: Tue Jul 31, 2012 6:22 am

by GARTHWILSON

How about:

Code: Select all

HIBIT: LDA  #0
       SEC
       BEGIN
          ROR  A
          ASL  INPUT
       UNTIL_C_SET

or the same thing, non-structured:

Code: Select all

HIBIT: LDA  #0
       SEC
 hb1:  ROR  A
       ASL  INPUT
       BCC  hb1

Re: isolate the high bit of a byte

Posted: Tue Jul 31, 2012 6:25 am

by Dr Jefyll

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:

Code: Select all

HIBIT
 lda num
 and #$F0
 bne SKIP1
 lda num        ;was: eor num
SKIP1
 sta temp
 and #$CC
 bne SKIP2
 lda temp       ;was: eor temp
SKIP2
 sta temp
 and #$AA
 bne SKIP3
 lda temp       ;was: eor temp
SKIP3
 rts

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.

Code: Select all

HIBIT
 lda num
 and #$F0
 bne SKIP1
 lda num                            ;was: eor num
SKIP1
 tay              ;was: sta temp
 and #$CC
 bne SKIP2
 tya              ;was: lda temp    ;was: eor temp
SKIP2
 tay              ;was: sta temp
 and #$AA
 bne SKIP3
 tya              ;was: lda temp    ;was: eor temp
SKIP3
 rts

BigEd wrote:

I haven't fully tested this.

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

Re: isolate the high bit of a byte

Posted: Tue Jul 31, 2012 5:31 pm

by BigEd

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

Re: isolate the high bit of a byte

Posted: Fri Oct 23, 2015 3:55 pm

by BigEd

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.

Re: isolate the high bit of a byte

Posted: Sat Oct 24, 2015 7:27 am

by Omegamatrix

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:

Code: Select all

 lda num
 and #$F0
 bne SKIP1
 eor num
SKIP1

To this:

Code: Select all

 lda num
 cmp #$10
 bcc SKIP1
 and #$F0
SKIP1

Re: isolate the high bit of a byte

Posted: Sun Oct 25, 2015 2:54 pm

by BitWise

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.

Code: Select all

 lda NUM
Loop:
 dec a
 and NUM
 beq Done
 sta NUM
 bra Loop
Done:

Utterly untested

Re: isolate the high bit of a byte

Posted: Sun Oct 25, 2015 3:10 pm

by nyef

BitWise wrote:

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.

Code: Select all

 lda NUM
Loop:
 dec a
 and NUM
 beq Done
 sta NUM
 bra Loop
Done:

Utterly untested

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

Re: isolate the high bit of a byte

Posted: Sun Oct 25, 2015 3:22 pm

by BitWise

nyef wrote:

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.

Code: Select all

Loop:
 sta NUM
 dec A
 and NUM
 bne Loop

Re: isolate the high bit of a byte

Posted: Sun Oct 25, 2015 4:32 pm

by Dr Jefyll

BitWise wrote:

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

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.

Omegamatrix wrote:

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.

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.

Code: Select all

HIBIT: ;previous version
 lda num
 and #$F0 ; <- destructive test
 bne SKIP1
 lda num
; [etc ]

Code: Select all

HIBIT: ;improved version
 lda num
 bit #$F0 ; <- non-destructive test
 beq SKIP1
 and #$F0
SKIP1:   ;if any of bits 7,6,5,4 is set then bits 3,2,1,0 have now been cleared 
 tay
 and #$CC
 bne SKIP2
 tya
SKIP2:   ;if any of bits 7,6,3,2 is set then bits 5,4,1,0 have now been cleared 
 tay
 and #$AA
 bne SKIP3
 tya
SKIP3:   ;if any of bits 7,5,3,1 is set then bits 6,4,2,0 have now been cleared 
 rts

-- Jeff

Re: isolate the high bit of a byte

Posted: Sun Oct 25, 2015 6:29 pm

by Omegamatrix

Dr Jefyll wrote:

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