Can someone explain this bit manipulation code?

Question

I have a tree control with checkboxes next to each node that allows for checked, unchecked and middle checked states on the nodes. When clicking a node, the parent and children are updated. The code I found that does the trick uses bit shifting and I'm trying to understand what exactly is happening.

Can someone explain the following code? Or even better, rewrite this code so it is easier to understand?

// click event handler
private function eventMessageTree_itemCheckHandler(event:TreeEvent):void {
  var node:ITreeNode = ITreeNode(event.item);
  var checkState:uint = TreecheckboxItemRenderer(event.itemRenderer).checkBox.checkState;
  updateParents(node, checkState);
  updateChilds(node, checkState);
}

private function updateChilds(item:ITreeNode, value:uint):void {
  var middle:Boolean = (value & 2 << 1) == (2 << 1);
  var selected:Boolean = (value & 1 << 1) == (1 << 1);

  if (item.children.length > 0 && !middle) {
    for each (var childNode:ITreeNode in item.children)     {
      childNode.checked = value == (1 << 1 | 2 << 1) ? "2" : value == (1 << 1) ? "1" : "0";
      updateChilds(childNode, value);
    }
  }
}

private function updateParents(item:ITreeNode, value:uint): void {
  var checkValue:String = (value == (1 << 1 | 2 << 1) ? "2" : value == (1 << 1) ? "1" : "0");
  var parentNode:ITreeNode = item.parent;
  if (parentNode) {
    for each (var childNode:ITreeNode in parentNode.children) {
      if (childNode.checked != checkValue) {
        checkValue = "2";
      }
    }
    parentNode.checked = checkValue;
    updateParents(parentNode, value);
  }    
}

Answer 1

Basically, an expression like this:

var middle:Boolean = (value & 2 << 1) == (2 << 1);

Is counter-intuitive. You usually test bits by shifting the constant 1 to the left, since that lets the number of bits shifted be the same as the index of the bit, counting the LSB (rightmost) bit as bit number 0.

Also, there's no point in testing the result with a == comparison, since it's always going to be either 0 or non-zero, so you can at least test for something simpler if your language requires that.

In C and C++, which by default interpret a non-zero integer as "true", the comparison is totally unnecessary and just serves to introduce clutter, repetition, and increase the risk of bugs.

I'd write this like so:

var middle:Boolean = (value & (1 << 2)) != 0;

The extra parenthesis should help make it clearer how things are grouped. Note how "2 << 1" was rewritten as "1 << 2". This is not just a "switch", you need to compute the proper shift to get the same bit value, 4 in this case.

Of course you could put the bit-testing into subroutines and call them, to make the code more readable.

Answer 2

It looks like the checkState value in the control can be either 1, 2, or 4 (or possibly 0, 2, and 4?):

public static const CONTROL_UNCHECKED:uint = 1; // not checked, and some descendants are
public static const CONTROL_CHECKED:uint = 2; // checked, and all descendants are
public static const CONTROL_MIDDLE:uint = 4; // not checked, but some descendants are

while the checked value in the nodes can be either 0, 1, or 2:

public static const UNCHECKED:uint = 0; // not checked, and some descendants are
public static const CHECKED:uint = 1; // checked, and all descendants are
public static const MIDDLE:uint = 2; // not checked, but some descendants are

That's really confusing. Ideally these would be the same set of constants.

To update:

private function controlStateToNodeState(value:uint):uint {
   return value / 2;
}
   ...
   updateParents(node, controlStateToNodeState(checkState));
   updateChilds(node, controlStateToNodeState(checkState));
   ...

/** Updates the descendants of the node based on state:
 *  If value is CHECKED, all children are CHECKED
 *  If value is UNCHECKED, all children are UNCHECKED
 *  If value is MIDDLE, children are left alone
 */
private function updateChilds(item:ITreeNode, value:uint):void {
   if (value == MIDDLE) {
      return;  // if value is MIDDLE, children are left alone
   }

   // not middle, so update all children to my state
   for each (var childNode:ITreeNode in item.children)     {
      childNode.checked = value;
      updateChilds(childNode, value);
    }
  }
}

/**
 * Updates the ancestor nodes based on state:
 * If value is CHECKED, ancestors are made MIDDLE if not already checked
 * If value is MIDDLE, ancestors are made middle (they should not already be CHECKED)
 */
private function updateParents(item:ITreeNode, value:uint): void {
    ...
}