The C ! operator

In C, the ! (“logical NOT”) operator used on a value x evaluates to 0 when x is not 0, and 1 when x is 0. In other words, it’s equivalent to the following C:

(x == 0) ? 1 : 0

How should this be implemented in x86 assembly language, when “x” is already in a register? The target register can either be the same one, or it can be a different one. I didn’t try too hard and got 7 bytes; it can probably be made better. On other CPUs, it can be done in a single instruction. For example, in MIPS: “sltiu dest, src, 1″.

Note that this is about the case where the compiler doesn’t know how the result of the ! is used, as in “return !x;” in a non-inlined function. Cases like “if (!x)” are simpler.

(If you want to share how easily it can be done on *your* favorite CPU, please post a comment as well!)

16 thoughts on “The C ! operator

  1. balial

    Alex, I don’t understand how your solution is supposed to work?

    not eax gives you the logical not of eax, and changes no flags

    sbb eax, eax results in 0 or -1, depending on the value of CF (which could be anything). Even if CF were set, the puzzle is for 0 or 1.

    tamlin, how small do you think you can get it with cmov?

    Reply
  2. myria

    So Alex’s should really be:
    not eax
    sbb eax, eax
    neg eax

    6 bytes. Still better than mine.

    cmov is certainly allowed in certain situations, like when you know everyone will have a Pentium Pro or later / Athlon or later. Also, all x86-64 processors support cmov, so it’s certainly allowable in x86-64.

    Reply
  3. myria

    Actually, Alex’s should be:
    neg eax
    sbb eax, eax
    neg eax

    neg sets the flags as if it were really doing 0 – eax.

    Reply
  4. balial

    Almost, myria, but that doesn’t seem right. That seems to give you a “logical identity”, that is, (eax==0) -> 0, (eax!=0) -> 1

    … of course, you could fix that easily by adding a logical not ;)

    Reply
  5. balial

    … or you could just change the 2nd neg to an inc, yielding:

    neg eax
    sbb eax, eax
    inc eax

    I *think* that’d do it – 5 bytes!

    Reply
  6. Michael Steil

    Just some brainstorming: Do you think something like this could be fast?

    test eax, eax
    mov eax, 0
    setz al

    Reply
  7. myria

    It’s hard to say without profiling. Pentium 4′s tend to react badly to operations involving flags.

    The “mov eax, 0″ is kinda big, requiring 5 bytes. This would work better:
    test eax, eax
    setz al
    and eax, 1

    for 8 bytes instead of 10. If the source and destination registers can differ, do this for 7 bytes:
    xor eax, eax
    test ebx, ebx
    setz eax

    balial’s suggestion seems the best, and actually works unlike mine and Alex’s: 5 bytes on x86-32 and 6 bytes on x86-64 (9 if 64-bit registers or r8-r15 are used).

    Reply
  8. Michael Steil

    @myria: Your test/setz/and solution is certainly shorter than my test/mov/setz – but your solution has two data dependencies, and mine has only one. I agree that using two registers is the best of both worlds. Anyway, I think this quiz was about size, not about speed.

    Reply
  9. Alex Ionescu

    Yeah sorry, I was a bit tired, I meant to post

    neg eax
    sbb eax, eax

    However I didnt realize this was for 0 or 1, so adding the inc eax is required… for a total of 5 bytes. Thanks for spotting that Balial.

    Reply
  10. Oliver

    What about this:

    LD A, ValX
    OR A, A

    Zero flag has now the result of !ValX.

    JR NZ, ValXisOne
    JR Z, ValXIsZero

    Hmmm, is this a valid solution?

    Reply
  11. mirabilos

    Hm, I get 8 bytes for the 32 bit case:

    8048378: 09 c0 or eax,eax
    804837a: 0f 94 c0 sete al
    804837d: 66 98 cbw
    804837f: 98 cwde

    Source (inline gcc asm hack, for simplicity):

    #include

    extern int inot(int);

    __asm__(“.globl inot”
    “n .intel_syntax noprefixn”
    “inot: mov eax,[esp+4]”
    “n or eax,eax”
    “n setz al”
    “n cbw”
    “n cwde”
    “n ret”
    “n .att_syntax”);

    int main(void) {
    int i;
    i = 0; printf(“%d -> %dn”, i, inot(i));
    i = 1; printf(“%d -> %dn”, i, inot(i));
    i = 2; printf(“%d -> %dn”, i, inot(i));
    i = 0xfffe; printf(“%d -> %dn”, i, inot(i));
    i = 0xffff; printf(“%d -> %dn”, i, inot(i));
    return 0;
    }

    In the 16-bit (but i386 insns allowed) case it’ll probably come
    down to much less (cwde can be skipped). I think it’ll amount to:

    09 C0 / 0F 94 C0 / 98
    or ax,ax
    sete al
    cbw

    Reply
  12. gds

    Am try to determine if c compilers guarantee that !0 is 1 and not some other non-zero number like 2 or -1. Is this called out in a C specification? The compiler I am currently using returns 1 for !0 but I don’t know if this is universal.

    -gene

    Reply
  13. gobsmacked

    You have to be kidding don’t you? You are requesting the compiler produce code that guarantees !0 == 1? Look at the logic presented here… NOT 0…

    Take the value 0×00000000 and perform a logical NOT (that is, invert every bit so 1 becomes 0 and vice-versa). 0xFFFFFFFF is your result.

    It is definitely not the ’1′ value you were expecting but it is also definitely not ’0′. This is a bitwise logical not.

    Now lets look at another possible context, where an unmentioned comparison value is supplied. Then it would be testing whether or not the value was equal to 0. ANY value other than 0 would be a valid value, providing that datatype supports it from the compiler aspect, assembler is a matter of any 32 bit value other than 0×00000000.

    Do you people even bother to engage your brains and think your ‘question’ through before putting fingers to keyboard?

    Reply
  14. Alex Nesemann

    The person above doesn’t understand how logic operations work in C (or it’s decedents) at all.

    Preforming a C logical not (!) needs to transform a non-zero value to a zero value. A bitwise inverse (~) only generates a zero if every bit in the source is a one; if the source has a mix of zero and one bits (which would be a true value), the result will still have a mix of zero and one bits (which is still a true value).

    Anyways, for the SuperH CPU, the ! operator can be done in two instructions:
    TST src,src (Set T bit in status register to 1 if src is != 0, or 0 if src == 0)
    MOVT dst (Move T bit to dst, top 31 bits of dst are always cleared)

    The TST instruction works backwards from how you would expect it. It doesn’t do, say, a 68K style TST and set the T bit to the 68K’s Z bit, but instead sets the inverse, allowing for simpler implementation of the C logical not outside of condition statements.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>