What does `(i & (i + 1)) - 1` mean? (in Fenwick Trees)

Question

While learning about Fenwick Trees, I found this implementation:

Source: https://algorithmist.com/wiki/Fenwick_tree

class Fenwick_Tree_Sum
{
    vector<int> tree;
    Fenwick_Tree_Sum(const vector<int>& Arg)//Arg is our array on which we are going to work
    {
        tree.resize(Arg.size());
        
        for(int i = 0 ; i<tree.size(); i++)
            increase(i, Arg[i]);
        
    }

    // Increases value of i-th element by ''delta''.
    void increase(int i, int delta)
    {
        for (; i < (int)tree.size(); i |= i + 1)
            tree[i] += delta;
    }

    // Returns sum of elements with indexes left..right, inclusive; (zero-based);
    int getsum(int left, int right)
    {
        return sum(right) - sum(left-1); //when left equals 0 the function hopefully returns 0
    }

    int sum(int ind)
    {
        int sum = 0;
        while (ind>=0)
        {
            sum += tree[ind];
            ind &= ind + 1;
            ind--;
        }
        return sum;
    }
};

I can see i |= i + 1 and ind &= ind + 1; ind-- in the code.

I know that i |= i + 1 just sets the next unset bit.

But, what does (i & (i + 1)) - 1 actually do?

Here are some examples:

-------------------------------------
         i        | (i & (i + 1)) - 1
-------------------------------------
  0 - 0000000000  |  -1 - 1111111111
  1 - 0000000001  |  -1 - 1111111111
  2 - 0000000010  |   1 - 0000000001
  3 - 0000000011  |  -1 - 1111111111
  4 - 0000000100  |   3 - 0000000011
  5 - 0000000101  |   3 - 0000000011
  6 - 0000000110  |   5 - 0000000101
  7 - 0000000111  |  -1 - 1111111111
  8 - 0000001000  |   7 - 0000000111
  9 - 0000001001  |   7 - 0000000111
 10 - 0000001010  |   9 - 0000001001
 11 - 0000001011  |   7 - 0000000111
 12 - 0000001100  |  11 - 0000001011
 13 - 0000001101  |  11 - 0000001011
 14 - 0000001110  |  13 - 0000001101
 15 - 0000001111  |  -1 - 1111111111
 16 - 0000010000  |  15 - 0000001111
 17 - 0000010001  |  15 - 0000001111
 18 - 0000010010  |  17 - 0000010001
 19 - 0000010011  |  15 - 0000001111
 20 - 0000010100  |  19 - 0000010011
 21 - 0000010101  |  19 - 0000010011
 22 - 0000010110  |  21 - 0000010101
 23 - 0000010111  |  15 - 0000001111
 24 - 0000011000  |  23 - 0000010111
 25 - 0000011001  |  23 - 0000010111
 26 - 0000011010  |  25 - 0000011001
 27 - 0000011011  |  23 - 0000010111
 28 - 0000011100  |  27 - 0000011011
 29 - 0000011101  |  27 - 0000011011
 30 - 0000011110  |  29 - 0000011101

Try evaluating this expression for several different values of `i` and see for yourself. Hint: display both `i` and the result in binary. — n. m. could be an AI, Oct 13 '20 at 12:30
...which you could do with `std::cout << std::bitset<8>(i) << "\t" << std::bitset<8>((i & (i + 1)) - 1) << "\n";` if you keep `i` to 8 bits. In other words, it does something strange. — Bathsheba, Oct 13 '20 at 12:36
I guess its purpose is to test whether all bits are set (except for leading zeros) in which case `-1` is returned. Or in other words: `i & (i + 1) == 0` — Andreas H., Oct 13 '20 at 12:42
From the context it looks like it navigates up the tree, and when you hit -1 you stop. So you could draw a graph of your output with every result = -1 as a root, and every other number a new node whose parent is the result. — Rup, Oct 13 '20 at 12:46
and from Wikipedia it sounds like the intention here is to remove the least significant bit of the input, i.e. binary 1011 -> 1010, 1010 -> 1000. However it doesn't look like your code actually does that from your output. — Rup, Oct 13 '20 at 12:57
@Rup no, the intention is to go to the next smaller index responsible for the sum. — n. m. could be an AI, Oct 13 '20 at 14:35
@n.'pronouns'm. OK, but ["that parent is found by clearing the least-significant bit in the index"](https://en.wikipedia.org/wiki/Fenwick_tree#Description). So it's the same thing. — Rup, Oct 13 '20 at 15:35

OmG · Accepted Answer · 2020-10-16T12:18:32.937

If the bit pattern of i is like ...0111, the bit pattern of i+1 will be ...1000. Hence, i & (i+1) means i - (2^{number of trailing ones} - 1) and transforming all trailing 1s to zero. For example if i is even, i & (i+1) will be equal to i. On the other hand, -1 means, transforming all trailing zeros to 1 (including all trailing ones to zeros of the previous step) and transforming the successive 1s to zeros.

By doing the -1 for the next step, i & (i+1) will decrease the i by the 2^{number of trailing 1's} of the previous value of the i.

What is the reason? It helps to show that the time complexity of finding the cumulative sum will be O(log n) in the worst case.

To find the reason behind this computation, you need to focus on each node i will responsible to compute index i to (i - (1 << r)) + 1. And "r represents the last 1 bit set in the index i". To find the total sum corresponding to index i, we need to sum all related values from 0 to i. Beware that we do not need to sum all indices because of the specified property. Hence, we need to sum indices i, i - (1 << r), ... and so on so forth.

Thanks! I see now what it's supposed to do, but what does this mean in the context of the attached code? — StackExchange123, Oct 13 '20 at 14:04
@StackExchange123 Please see the updated answer (the last paragraph). — OmG, Oct 13 '20 at 14:36
When you say "leading" I think you mean "trailing" throughout. Also, the `i - 2^[number of leading ones}` is off by one; `i & (i + 1)` is `i - 2^{number of trailing ones} + 1`. — Richard Smith, Oct 15 '20 at 23:31

What does `(i & (i + 1)) - 1` mean? (in Fenwick Trees)

1 Answers1