# Code advice with minimum clock cycles

My original question was:

I've a 8 bit data with only 3 bit used, for example:

0110 0001

Where 0 indicate unused bit that are always set to 0 and 1 indicate bits that change.

I want to convert this 0110 0001 8 bit to 3 bit that indicate this 3 used bits.

For example

0110 0001 --> 111

0010 0001 --> 011

0000 0000 --> 000

0100 0001 --> 101

How I can do that with minimal operations?

a = 0110 0001;

data = ((a >> 4) & 6) | (a & 1)


But before this answer I used this method:

a = 0110 0001;

if(a&0x01)
data = data + 1;
if(a&0x20)
data = data + 2;
if(a&0x40)
data = data + 4;


I want to ask which is more efficient for a MCU an require less clock cycle to perform. (I know that depend on MCU, but I'm asking in general way)

• "I know that depend on MCU, but I'm asking in general way" ehrm, what? – PlasmaHH Feb 24 '15 at 10:19
• You'll have to see the actual machine code emitted to make your decision. No matter how hard you think your compiler may surprise you. – sharptooth Feb 24 '15 at 10:24
• On an FPGA, this is trivial to do in one clock cycle. Difficult to get more minimal than that. – Brian Drummond Feb 24 '15 at 13:17

As @sharptooth mentions - the compiler really does have the final say. It also depends heavily on the architecture you're compiling for - what instructions it has available.

For instance, compiling your first snippet for MIPS results in:

sra v1,v0,0x4
andi    v1,v1,0x6
andi    v0,v0,0x1
or  v0,v1,v0


andi    v1,v0,0x1
beqz    v1,func+0x20
andi    v1,v0,0x20
lbu v1,-32760(gp)
sb  v1,-32760(gp)
andi    v1,v0,0x20
beqz    v1,func+0x34
andi    v0,v0,0x40
lbu v1,-32760(gp)
sb  v1,-32760(gp)
beqz    v0,func+0x44
lbu v0,-32760(gp)
sb  v0,-32760(gp)


So undoubtedly in this situation your first snippet is the more code efficient. The same may not always be true though for a different architecture or a different compiler.

There's also some other caveats to note with your second snippet. Chiefly, what is "data" at the start? You have to remember to always zero "data" out before doing your calculations, or you'll end up accumulating successive values. The same is not true for the first snippet.

As others have correctly said, "it depends".

On a Cortex M0, with the variables in memory, for your one-liner I get

 // data = ((a >> 4) & 6) | (a & 1)
ldrb   r1, [r2]
ldrb   r3, [r2]
mov    r2, #1
lsr    r1, r1, #4
and    r1, r4
and    r2, r3
mov    r3, r1
orr    r3, r2
strb   r3, [r5]


 // if's
mov    r3, sp
ldrb   r1, [r2]
lsl    r1, r1, #31
bpl    .L2
ldrb   r1, [r3]
uxtb   r1, r1
strb   r1, [r3]
.L2:
ldrb   r1, [r2]
lsl    r1, r1, #26
bpl    .L3
ldrb   r1, [r3]
uxtb   r1, r1
strb   r1, [r3]
.L3:
ldrb   r1, [r2]
lsl    r1, r1, #25
bpl    .L4
ldrb   r1, [r3]
uxtb   r1, r1
strb   r1, [r3]
.L4:


Yuk, that's ugly, isn't it? But on an architecture that has skip instructions (PIC) or conditional instructions (ARM) it might look much better.

My attempt would be

data = ((a >> 4 ) | a ) & 0x0F;

ldrb    r2, [r3, #7]
ldrb    r1, [r3, #7]
lsr r2, r2, #4
orr r2, r1
mov r1, #15
and r2, r1
strb    r2, [r3, #6]


Which turns out marginally better than your one-liner on this version of this compiler for this target and with this optimization settings.

I think I could even leave out the final "& 0x0F" which would save 2 instructions.

On the Microchip PIC, testing individual bits is generally the fastest approach if the source or destination are in the same bank, or if at least one of them is an unbanked region. On those machines, each conditional bit set operation will take two instructions (one for the "if", and one for the "bit set"). On the 8051, the fastest approach if source and destination are in bit-addressable memory will be to use "mov bit,C" and "mov C,bit" instructions.

On the ARM, the fastest "general" approach is apt to be using a combination of either RORS or ROLS and ADC. Such an approach can be used to permute bits in arbitrary fashion among registers and a cost of two cycles per bit. If, for example, one wanted to assemble a register R2 using (in LSB-first order) bits R0.3, R1.4, R0.8, and R1.7, the sequence would be something like:

rors r1,r1,#7 ; Move bit 7 to bit 0
ands r2,r1,#1  ; May need to split this into two instructions on some machines
rors r0,r0,#9 ; Move bit 8 into carry and bit 31