4

In an interrupt subroutine (called every 5 µs), I need to check the MSB of a byte and copy it to the rest of the byte.

I need to do something like:

if(MSB == 1){byte = 0b11111111}
else{byte = 0b00000000}

I need it to make it fast as it is on an interrupt subroutine, and there is some more code on it, so efficiency is calling.

Therefore, I don't want to use any if, switch, select, nor >> operands as I have the felling that it would slow down the process. If i'm wrong, then I'll go the "easy" way.

What I've tried:

byte = byte & 0b100000000

This gives me 0b10000000 or 0b00000000.

But I need the first to be 0b11111111.

I think I'm missing an OR somewhere (plus other gates). I don't know, my guts is telling me that this should be easy, but it isn't for me at this moment.

Jongware
  • 22,200
  • 8
  • 54
  • 100
SISKO
  • 43
  • 3
  • 3
    The conditional you have shown is really good enough. And it will be way more readable than any bit-hacking. – Eugene Sh. May 13 '16 at 19:40
  • Are you using C? Or, are you doing this in asm? If you do the signed right shift approach, check the ISA reference manual for your microcontroller for the arithmetic right shift opcode to be sure [it probably works]. Or, just create a test case. In C, just disassemble the code to be sure you get the expected opcode. – Craig Estey May 13 '16 at 20:18
  • @Craig Estey: Im using C. Thanks, ill have that in mind. – SISKO May 13 '16 at 21:36
  • @Eugene Sh: Since its on an interrupt subrutine, speed is more precious than clarity. If not, i would choose the conditional. – SISKO May 13 '16 at 21:36
  • This conditional will translate into ~3 machine instructions to execute. Mask, compare/jump, assign. Really, doesn't worth the hassle. – Eugene Sh. May 13 '16 at 21:38
  • 1
    Just tested this on x86, doing `m = (m & 0x80) ? 0xFF : 0x00`, with -O2 will cause the optimizer to generate a single `sar` inst (i.e. it _figured it out_). I presumed this was likely because I've seen similar "pinhole" optimizations before for useful/common constructs like this. So, ironically, your _first_ code example will generate optimal code ... – Craig Estey May 14 '16 at 00:14
  • @Craig Estey: Thats great to know! – SISKO May 16 '16 at 02:19

3 Answers3

3

EDIT: My answer has confused people because I did not specify unsigned bytes. Here my assumption is that B is of type unsigned char. As one comment notes below, I can omit the &1. This is not as fast as the signed byte solution that the other poster put up, but this code should be portable (once it is understood that B is unsigned type).

 B = -((B >> 7)&1)

Negative numbers our are friends. Shifting bits should be fast by the way.

TheGreatContini
  • 6,429
  • 2
  • 27
  • 37
  • It is not very portable – Eugene Sh. May 13 '16 at 19:36
  • @EugeneSh. What makes you think this is not portable? –  May 13 '16 at 19:38
  • 1
    negative `1` is not `111...1` in every representation. `C` does not guarantee 2's complement. – Eugene Sh. May 13 '16 at 19:40
  • I assumed unsigned type in my answer. Another poster has signed type and is more efficient than my answer. – TheGreatContini May 13 '16 at 19:47
  • 1
    Actually, you can omit the `&1` as a `B >> 7` of an unsigned byte is _only_ 1 or 0. And, any decent optimizer will probably transmute the code anyway. – Craig Estey May 13 '16 at 19:51
  • @user3386109 I've edited my answer to clarify that it is unsigned. – TheGreatContini May 13 '16 at 19:58
  • In a way, I like your answer better because it will work on _any_ of the eight bits (e.g. `B = -((B >> x) & 1`) where `x` is 0-7 [in which case, you _do_ need the and] whereas the signed shift approach only works on MSB – Craig Estey May 13 '16 at 20:04
  • Thank you very much! All of you. In particular, Craig Estey, your solution worked like a charm!! Thanks so much! And thanks to Rad Lexus for editing my post – SISKO May 13 '16 at 21:56
3

The trick is to use a signed type, such as int8_t, for your byte variable, and take advantage of sign extension feature of the shift-right operation:

byte = byte >> 7;

Demo.

Shifting right is very fast - a single instruction on most modern (and even not so modern) CPUs.

The reason this works is that >> on signed operands inserts the sign bit on the left to preserve the sign of its operand. This is called sign extension.

Note: Technically, this behavior is implementation-defined, and therefore is not universally portable. Thanks, Eugene Sh., for a comment and a reference.

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • That's cute. Make the bytes signed and it becomes trivial. Good answer. – TheGreatContini May 13 '16 at 19:44
  • 1
    The result of bit-shifting signed negative integers is implementation defined. http://port70.net/~nsz/c/c11/n1570.html#6.5.7p5 – Eugene Sh. May 13 '16 at 19:45
  • @EugeneSh. Thanks for the reference and a comment, I got so used to this being implemented as an arithmetic shift that I did not realize that it is implementation-defined. I edited the answer to include your reference. – Sergey Kalinichenko May 13 '16 at 19:52
  • Sometimes sign extension on non-`int` types requires more than one instruction: what's actually happening is that the compiler first shift left 24 bits then right shift 31. If that's the case, it's not any better than a conditional move after a compare. – user3528438 May 13 '16 at 20:04
  • @user3528438 OP operates on a single byte, though, so his embedded compiler should generate a single `ASR` instruction. – Sergey Kalinichenko May 13 '16 at 20:13
  • @dasblinkenlight That's not the case unless ASR can somehow operate on a byte. Most RISC-like machines I know the ASR can only work on a word, and integer promotion alone involves two shifts, although some can do two shifts with one instruction( e.g. EXT on TI C6000). – user3528438 May 13 '16 at 20:25
  • but it's not necessarily fast on microcontroller because most of them don't have a barrel shifter and can only shift one bit at a time – phuclv May 21 '16 at 04:02
  • @user3528438 the compiler is smart enough to not promote to int if not needed. as long as the result is still the same – phuclv May 21 '16 at 04:04
  • I am saying most CPUs are not capable of doing arithmetic right shift on a signed type that is narrower than its ALU. I believe ARM is one of them. – user3528438 May 21 '16 at 12:24
  • @user3528438 but RISC architectures like ARM have instructions to load and sign-extend the value to the register width, so there's actually no problem – phuclv May 22 '16 at 11:22
0

The MSB is actually the sign bit of the number. It is 1 for a negative number and 0 for a positive number. so the simplest way to do that is

if(byte < 0)
{
    byte = -1;
}
else
{
    byte = 0;
}

because -1 = 11111111 in binary.

If it is the case for an unsigned integer, then just simply type cast it into a signed value and then compare it again as mentioned above.

Waqas Shabbir
  • 755
  • 1
  • 14
  • 34
  • the value -1 is not necessary all 1 bits, because C allows the use of other signed formats like 1's complement and sign-magnitude – phuclv May 21 '16 at 04:05
  • @LưuVĩnhPhúc can you please give me an example? – Waqas Shabbir May 23 '16 at 03:03
  • -1 can be 11111110 in one's complement, 10000001 in sign-magnitude, assuming 8-bit bytes [Representation of negative numbers in C?](http://stackoverflow.com/q/3952123/995714) – phuclv May 23 '16 at 03:31
  • @LưuVĩnhPhúc, In both of your cases (one's complement or sign-magnitude) the MSB remains the same (i.e. 1 for a negative number). – Waqas Shabbir May 23 '16 at 12:53
  • no. right shift on signed type in C is [implementation defined behavior](http://stackoverflow.com/q/8422424/995714). If signed bit is always filled in then -1 might become -0 or -64 for one's complement and sign-magnitude – phuclv May 23 '16 at 14:48