The complement of true is true, except when it's false | Hacker News Reader

The complement of true is true, except when it's false

dryperspective.github.io

69 pointsaw162110726 comments

With such example:

  bool Complement( bool x )
  {
      return ~x;
  }

GCC gives a warning if compiling with -Wall:

  test.cpp:3:10: warning: ‘~’ on an expression of type bool [-Wbool-operation]
    return ~x;

So, it's surprise that C++ does this, but ones who enable compiler warnings are not in trouble.

They should have defined true as -1 (all bits set) instead, as in some other languages like Forth and BASIC.

-1 is not -1 for different sizes of integers. Which exact -1 do you want? 32-bit? 64-bit? int-sized (as int is defined in current implementation)? With current approach it's simple, boolean type is expected to have 1-bit size (which is rounded to 8 bits if stored in memory).

You have some expectations of the size of the bool (it's simply 1 bit but also 8 bits.)

What expectations do you have of the value?

Bool should be logically 1-bit, when stored in memory only least significant bit should be used and the rest is allowed to be garbage. Such approach gives compilers as much room for optimizations as possible. Forcing them writing some specific bit-pattern may lead to suboptimal code generation.

That's how gcc does it (at least in this one case), but as TFA points out, this is not standard-conforming.

The in-memory representation is a completely different question. The language could easily say that true has an integer value of -1 while still storing it as a single bit.

Bool is 1-bit, but that bit can be defined as signed or as unsigned.

If bool is defined as unsigned, casting it to any size of integers will give 0 for false and 1 for true (using the standard zero-extension operation that converts smaller unsigned integers to bigger unsigned integers).

If bool is defined as signed, casting it to any size of integers will give 0 for false and -1 for true (i.e. an all-1 bit pattern) (using the standard sign-extension operation that converts smaller signed integers to bigger signed integers).

Defining bool to ignore the other bits except the LSB leads to a lower performance on most processors, because in almost all instruction sets it is more efficient to test whether an integer is null or non-null, than to test the value of a bit.

The only efficient way to use a single bit and to ignore the others would be to store the boolean in the most-significant bit, i.e. in the sign bit of a signed integer, because testing the sign is normally as simple as testing whether a value is null. If this convention were used, a boolean result could be 0 for false and -1 for true, but in input arguments negative would be true and non-negative would be false.

x86-64 and ARM64, at least, let you test an arbitrary bit in a register with one instruction.

The fact that bit testing also needs one instruction does not mean that it is equally efficient.

On x86-64, there are 2 ways to test the value of a bit. If you use the bit testing instruction (BT), that instruction is both longer and slower than testing if a register or memory value is null.

If you use the test-under-mask instruction (TEST), this is fast, but the instruction is significantly longer (by including an immediate constant for the mask). Longer instructions can also cause lower speeds, when various bottlenecks are encountered, e.g. the maximum number of bytes fetched per clock cycle or the capacity of the instruction cache or of the micro-operation cache.

Moreover, testing whether a value is null frequently requires zero instructions, not one instruction, because if the value is the result of computing some expression then the flags register already stores if the value is null or not (and its sign).

On ARM Aarch64, the instruction that tests a bit in a register has a much smaller jumping range than the one that tests whether the whole register is null, so testing a bit in a register may require the insertion of an extra jump instruction to reach the target where execution should continue.

Once upon a time testing whether all bits of a number are zero was slower than checking a single sign bit. Even when MIPS was originally designed, Hennessy and his team had some trouble with making BEQZ/BNEZ fast enough for their intended pipeline.

This happens because testing the sign bit needs just a wire from that bit to the flags, while testing if a register is zero requires a wide OR gate with as many inputs as there are bits.

In CMOS you cannot have an OR gate so wide, so it must be synthesized from a cascade of narrower gates, which add several levels of delays.

While in modern CPU technologies the speed of generating a zero flag is not a problem, when designing with FPGAs, which are much slower, it is useful to be aware that testing for the sign is cheaper than testing for a wide zero.

Many CPUs have an instruction for implementing loops like decrement-and-jump-if-not-zero (which is LOOP in x86-64). When implementing a simple CPU in an FPGA it is cheaper and faster to replace that instruction with 2 instructions for loops like increment-and-jump-if-negative and decrement-and-jump-if-not-negative (it is good to have both these instructions to be able to access an array both in forward order and in reverse order, while using the loop counter also as index register).

The same applies when making a counter in FPGAs, it can count at higher frequencies if you test for the sign bit to determine the end of the counting, instead of testing when the count reaches zero.

« to test whether an integer is null or non-null »

Shouldn't this more correctly read zero or non-zero ?

Null and zero are synonymous, but null is preferable when used as an adjective and zero is preferable when used as a noun.

There are 2 words for the same concept because "null" comes from Latin, while "zero" comes from Sanskrit through Arabic.

Etymologically, "null" means "not even one" (by being a diminutive form of "not one").

The use of "null" in some programming languages to mean things like "undefined", "not applicable" or "nothing" is incorrect. For those the right choice is NIL, as in LISP (NIL means nothing).

While LISP had made the right choice by using NIL, it made later the mistake of calling NULL the predicate that tests if something is NIL. That predicate should have been called something like "is_nil".

When C.A.R. Hoare had introduced the word "null", he applied "null" to references, i.e. to pointers, not to the things pointed by those pointers. So a "null" pointer, whose value is zero, points to NIL, i.e. to nothing, and this is an alternative to devising an encoding for the things that are pointed to, where a special value is reserved to encode NIL (like the Not-a-Number values of floating-point numbers).

I presume you didn't make all that up, but which authorities did you consult and under which circumstances would which audience immediately agree with you on all points?

In British English nil means zero as in a nil-nil draw in football. In this case it is effectively an ordinal number and it means none, not nothing.

This reminds me of my favorite arcane C test: what value is TRUE and FALSE on X bullshit tool chain. My a favorite was 0=TRUE, 2=FALSE. I'd like to shake the hand of the joker who came up with that.

I vaguely remember that Clang and GCC used to disagree what the contents of the upper parts of x64 registers when returning some integer types should be (zeroes or garabge), because the PDF that defined Sys V ABI on x64 left such irrelevant details out, so linking together objects produced by those compilers, both of which claimed to follow the same ABI, would produce malfunctioning executable.

> Forcing them writing some specific bit-pattern may lead to suboptimal code generation.

So? Forcing them to compile "return 42;" as "mov eax, 42; ret" also leads to suboptimal code generation: a plain "ret", returning whatever is in rax already, is optimal. It doesn't generate the specific bit pattern for 42 but that's a small price for the improved efficiency, isn't it?

If bool was a signed 1-bit type (i.e. having possible values of either 0 or -1), it could be extended to any size, same as an integer?

Of course we can't have that now, because unsigned bool is baked into the C language standard, and even into processors (x86 SETcc instruction). While "char" being signed or not is still implementation-defined IIRC...

The obvious fix is to allow programmers to opt into this by writing `signed bool`.

In any field of characteristic 2, every element is its own negative. So on the surface this makes sense, notwithstanding the unintuitive enum corner case behaviour

The article is about the complement, not the negative.

C++ is a true spiritual successor to Perl, in a way. It can express anything and everything, its syntax is arcane, as is its logic. Most of the time, of course, what you see is what you get, until the moment when what you see is what you don't get.

While I understand why C++ defines bool as an Integer, it might have been better if it wasn't. It's not a problem for me that in some modern languages, boolean cannot be mixed with numbers in an expression.

I wonder if [[=std::bitmask_type]] also enables compiler warnings that a switch statement is not exhaustive if it does not cover all possible flag combinations.

I thought attributes were reserved for compiler-specific semantics like calling conventions. Here they're just being used as stropping for a language feature with syntactic significance!

It's not an attribute, it's an annotation. Annotations start with [[= .

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p33...

Reply on news.ycombinator.com