I’m learning about the Binary Indexed Trees, and I understand how it works, but I’m interested in the theory that there is behind!
In particular, I don’t understand what is meant the following definition on TopCoder
The algorithms for BIT require extracting the last bit of a number, so we need an efficient way of doing that. Let num be an integer. We will now show how to isolate the last bit of num. In binary notation num can be represented as a1b, where a represents binary digits before the last bit and b represents zeroes after the last bit.
My first question what is mean
In addition, I don’t understand what is mean this definition
Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have
-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = ¯0(1…1) + 1 = a¯1(0…0) = a¯1b.
Someone can help me?