CODEWITHSUNDEEP
c++20undefined-behaviortwos-complementbinary-operatorsimplementation-defined-behavior
mbang
mbang

Reputation: 855

Computing indices in Fenwick tree/Binary Indexed Tree (BIT)

The Fenwick tree data structure requires a member function read. For a index idx, read must compute several indices idx[0], idx[1], idx[2], ..., idx[last]. Each idx[i] will be the value that results when you set the i least significant non-zero bits of idx to 0.

For example, if idx = 13 = ...00001101, then idx[1] = 13, idx[1] = 12 = ...00001100, and idx[2] = 8 = ...00001000.

If we assume, as most online sources on Fenwick trees do, that signed integers are represented using two's complement, idx[i] is easy to compute. In that case, idx[i+1] = idx[i] - (idx[i] & -idx[i]);. Justification for this line can be found here: Fenwick trees.

Prior to C++20, using bitwise & was implementation defined, but it appears C++20 now requires the use of two's complement. That leads to the following questions:

  1. Is it correct to say that, prior to C++20, idx[i+1] = idx[i] - (idx[i] & -idx[i]); is "incorrect" code?
  2. With C++20, is idx[i+1] = idx[i] - (idx[i] & -idx[i]); now correct?
  3. If the answer to (2) is "no", what is an efficient way to compute idx[]? If idx is unsigned, can I just do idx[i+1] = idx[i] - (((~idx[i]) + 1) & idx[i])?

Upvotes: 0

Views: 70

Answers (1)

user555045
user555045

Reputation: 64904

If idx is unsigned, can I just do idx[i+1] = idx[i] - (((~idx[i]) + 1) & idx[i])?

In fact if idx is unsigned you can just do idx[i+1] = idx[i] - (idx[i] & -idx[i]);, so you can get the best of both worlds.

Contrary to popular myth, negating unsigned integers is well-defined, and moreover it does exactly what you need it to do here.

This has always been safe, and it's always convenient. There is no need to rewrite the negation.

From the C++ specification:

The operand of the unary - operator shall have arithmetic or unscoped enumeration type and the result is the negation of its operand. Integral promotion is performed on integral or enumeration operands. The negative of an unsigned quantity is computed by subtracting its value from 2n, where n is the number of bits in the promoted operand. The type of the result is the type of the promoted operand.

Upvotes: 0

Related Questions