0

I have seen in many c++ codes (like the fenwick tree) that x & -x is used. For instance:

int sum(int idx) 
{
        int ret = 0;
        for (idx++; idx > 0; idx -= idx & -idx) // here!
            ret += bit[idx];

        return ret;
}

So:

  • What is the meaning of this and what will it cause to happen? (And what are the situations I can use this)
  • Why this happens and how?
  • In which programming languages is this implemented?
  • Is there any situations that this will cause a problem or don't work properly?
amirali
  • 1,888
  • 1
  • 11
  • 32
  • How can it not work properly if you don't what it does, or what it is supposed to do? – Scott Hunter Jul 12 '19 at 12:21
  • @ScottHunter I can guess this is a bit trick of course, and I can guess there may be some situations which this doesn't work properly. May I ask what is the purpose of your question?! – amirali Jul 12 '19 at 12:27
  • `x & -x` is the *rightmost* bit set to `1`, e.g. `0b101110 -> 0b10`, `0b11000 -> 0b1000`, `0b1101 -> 0b1` – Dmitry Bychenko Jul 12 '19 at 12:27
  • Also see this answer https://stackoverflow.com/a/12819032/1791872 – flau Jul 12 '19 at 12:28
  • Since nobody actually described the effect in the actual example (concentrating on the general meaning rather than the specific effect here), I present this analysis: `idx & -idx` is the least significant 1 bit in idx (Dmitry Bychenko). Thus, `idx -= idx & -idx` clears the least significant 1 bit (no borrow for `1 - 1`). The for loop then iterates through all the 1 bits adding an element of bit[] to res (which element depends upon the initial value of idx) until all the 1s have been cleared. As for which programming languages, just about all (one way or another, c.f. Turing's Thesis) Intercal? – Uber Kluger Sep 25 '20 at 09:56

0 Answers0