39

This is awkward, but the bitwise AND operator is defined in the C++ standard as follows (emphasis mine).

The usual arithmetic conversions are performed; the result is the bitwise AND function of its operands. The operator applies only to integral or unscoped enumeration operands.

This looks kind of meaningless to me. The "bitwise AND function" is not defined anywhere in the standard, as far as I can see.

I get that the AND function is well-understood and thus may not require explanation. The meaning of the word "bitwise" should also be rather clear: the function is applied to corresponding bits of its operands. However, what constitute the bits of the operands is not clear.

What gives?

Jared Burrows
  • 54,294
  • 25
  • 151
  • 185
R. Martinho Fernandes
  • 228,013
  • 71
  • 433
  • 510
  • Keep reading. There are more paragraphs in the question. – R. Martinho Fernandes Apr 01 '15 at 16:47
  • 4
    @R.MartinhoFernandes - Well, it first depends on the relative precedence of `-` and `&`, and the coercion rules, which I always have to double-check for a given language. But if `-1` is interpreted as being calculated first, in 2s complement, and coercion leaves the value unchanged then it would be `0xFFFFFFFF & 0x00000002`, or simply 2. – Hot Licks Apr 01 '15 at 17:32
  • 3
    So you thought it was ok to make all those assumptions that C++ doesn't specify? Well, in fact, you actually ignored the parts that C++ does specify: unary minus has higher precedence than bitwise and. – R. Martinho Fernandes Apr 01 '15 at 17:33
  • 2
    @HotLicks: C does not specify twos complement, nor does C++ IIRC. – Kevin Apr 01 '15 at 17:34
  • 1
    @R.MartinhoFernandes - I said I haven't checked. And there are many things that are not officially documented in C++ which if you changed would break thousands if not millions of programs. – Hot Licks Apr 01 '15 at 17:35
  • I said I hadn't checked. – Hot Licks Apr 01 '15 at 17:35
  • 3
    The point is that whether a comp sci student has a general idea of what "bitwise AND" means is not relevant. Actually, if they are aware of what "bitwise AND" means, I expect them tp be able to spot the underspecified parts, or at least realise that they are making unspecified assumptions. – R. Martinho Fernandes Apr 01 '15 at 17:36
  • 3
    No, the standard does not specify twos-compliment for negatives. But it DOES specify binary representation for positives. That is, 9 will always be 1001, and 3 will always be 11, so 9 & 3 will always be 11. No gray code, BCD need apply. – Lee Daniel Crocker Apr 01 '15 at 23:41
  • Does C++ permit padding bits or extraordinary values (most negative for twos complement, negative zero for sign magnitude or ones complement)? C explicitly permits bitwise operators, and only bitwise operators, to return a negative zero for ones complement and sign magnitude implementations, but I can't find any relevant language in the C++ standard. – Random832 Apr 28 '15 at 19:58
  • Two's complement is guaranteed since C++20 and C23 – Weijun Zhou Oct 11 '21 at 13:48

4 Answers4

39

This is underspecified. The issue of what the standard means when it refers to bit-wise operations is the subject of a few defect reports.

For example defect report 1857: Additional questions about bits:

The specification of the bitwise operations in 5.11 [expr.bit.and], 5.12 [expr.xor], and 5.13 [expr.or] uses the undefined term “bitwise” in describing the operations, without specifying whether it is the value or object representation that is in view.

Part of the resolution of this might be to define “bit” (which is otherwise currently undefined in C++) as a value of a given power of 2.

and the response was:

CWG decided to reformulate the description of the operations themselves to avoid references to bits, splitting off the larger questions of defining “bit” and the like to issue 1943 for further consideration.

and defect report 1943 says:

CWG decided at the 2014-06 (Rapperswil) meeting to address only a limited subset of the questions raised by issues 1857 and 1861. This issue is a placeholder for the remaining questions, such as defining a “bit” in terms of a value of 2n, specifying whether a bit-field has a sign bit, etc.

We can see from this defect report 1796: Is all-bits-zero for null characters a meaningful requirement?, that this issue of what the standard means when it refers to bits affected/affects other sections as well:

According to 2.3 [lex.charset] paragraph 3,

The basic execution character set and the basic execution wide-character set shall each contain all the members of the basic source character set, plus control characters representing alert, backspace, and carriage return, plus a null character (respectively, null wide character), whose representation has all zero bits.

It is not clear that a portable program can examine the bits of the representation; instead, it would appear to be limited to examining the bits of the numbers corresponding to the value representation (3.9.1 [basic.fundamental] paragraph 1). It might be more appropriate to require that the null character value compare equal to 0 or '\0' rather than specifying the bit pattern of the representation.

There is a similar issue for the definition of shift, bitwise and, and bitwise or operators: are those specifications constraints on the bit pattern of the representation or on the values resulting from the interpretation of those patterns as numbers?

In this case the resolution was to change:

representation has all zero bits

to:

value is 0.

Note that as mentioned in ecatmur's answer the draft C++ standard does defer to C standard section 5.2.4.2.1 in section 3.9.1 [basic.fundamental] in paragraph 3 it does not refer to section 6.5/4 from the C standard which would at least tell us that the results are implementation defined. I explain in my comment below that C++ standard can only incorporate text from normative references explicitly.

Community
  • 1
  • 1
Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
  • Can you comment on [basic.fundamental]/7 as mentioned by others? It seems to me that that nails down the behaviour. A value or sign bit in the value representation must correspond to a bit in the object representation, so it doesn't matter which representation you consider the operation to apply to. – M.M Apr 03 '15 at 03:04
  • @MattMcNabb I think the other two answers said about as much as can be said. I don't think it answers the question for negative numbers, except to say perhaps it should be implementation defined. Note that we can not refer to `6.5/4` from C99 since it is not explicitly referenced in the C++ standard see [Can we apply content not explicitly cited from the normative references to the C++ standard?](http://stackoverflow.com/q/23020323/1708801) – Shafik Yaghmour Apr 03 '15 at 20:04
  • 1
    If the standard made a stronger guarantee then the defect reports would not make much sense. – Shafik Yaghmour Apr 03 '15 at 20:20
  • With regard to the defect report related to null characters, I think the standard specifies clearing all the bits of an integer type must yield a legitimate representation of the value zero, though not necessarily the only one. As such, I would think the improvement of the standard loosens it, but not in a way that I can imagine compiler authors finding useful. How would the extra latitude benefit compilers? – supercat Apr 09 '15 at 20:36
  • @supercat as far as I can tell this was a way to avoid dealing with the fact that `bit` is not properly defined and the resolution to `df 1943` should fix that. – Shafik Yaghmour Apr 10 '15 at 11:49
  • @ShafikYaghmour: If the problem is that "bit" isn't really defined in this context, changing "all bits zero" to "all bytes zero" should fix that. Otherwise one could legitimately have a representation in which the end of a string literal wasn't marked with any zero `char` values [e.g. because wchar_t has padding bits which get set by the compiler] – supercat Apr 10 '15 at 13:32
9

[basic.fundamental]/3 defers to C 5.2.4.2.1. It seems reasonable that the bitwise operators in C++ being underspecified should similarly defer to C, in this case 6.5.10/4:

The result of the binary & operator is the bitwise AND of the operands (that is, each bit in the result is set if and only if each of the corresponding bits in the converted operands is set).

Note that C 6.5/4 has:

Some operators (the unary operator ~, and the binary operators <<, >>, &, ^, and |, collectively described as bitwise operators) are required to have operands that have integer type. These operators yield values that depend on the internal representations of integers, and have implementation-defined and undefined aspects for signed types.

The internal representations of the integers are of course described in 6.2.6.2/1, /2.

ecatmur
  • 152,476
  • 27
  • 293
  • 366
6

C++ Standard defines storage as a certain amount of bits. The implementation might decide what meaning to attribute to a particular bit; that being said, binary AND is supposed to work on conceptual 0s and 1s forming a particular type's representation.

3.9.1.7. (...) The representations of integral types shall define values by use of a pure binary numeration system.49 (...)

3.9.1, footnote 49) A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral power of 2, except perhaps for the bit with the highest position

That means that for whatever physical representation used, binary AND acts according to the truth table for the AND function (for each bit number i, take bits Ai and Bi from appropriate operands and produce a value of 1 only if both are 1, otherwise produce a 0 for the bit Ri).. Resulting value is left to interpret by the implementation, but whatever is chosen, it has to be in line with other expectations with regard to other binary operations like OR and XOR.

Community
  • 1
  • 1
Bartek Banachewicz
  • 38,596
  • 7
  • 91
  • 135
3

Legally, we could consider all bitwise operations to have undefined behaviour as they are not actually defined.

More reasonably, we are expected to apply common sense and refer to the common meanings of these operations, applying them to the bits of the operands (hence the term "bitwise").

But nothing actually states that. Shame my answer can't be considered normative wording.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • 6
    Sorry for the bad formatting... In 3.9.1 we find this: **A synonym for integral type is integer type. The representations of integral types shall define values by use of a pure binary numeration system.** and the pure binary numeration is defined in footnote as: **positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral power of 2, except perhaps for the bit with the highest position.** – fjardon Apr 01 '15 at 15:20
  • 1
    @fjardon: That final clause is rather important, no? – Lightness Races in Orbit Apr 01 '15 at 15:21
  • 2
    Yes it is, but I cannot see how it allows `(0 | 5)` to be something else than 5 knowing that int as more than 4 bits. I'm not saying you're wrong. I just want to understand. – fjardon Apr 01 '15 at 15:24
  • @fjardon: Well that might not have been the best example, in hindsight – Lightness Races in Orbit Apr 01 '15 at 15:24