c++bitbitmask

Given solution using Bitmask, I am unable to understand the evaluation of condition as marked in code


I an unable to understand the bit masking used here, the given code is a solution of finding no of palindrome paths in a binary tree which contains digits 0-9 inclusive. I have marked the line in code with in a if statement.

This is the question of LeetCode contest. Question is as given:

Pseudo-Palindromic Paths in a Binary Tree, Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

    int pseudoPalindromicPaths (TreeNode* root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode* root, int count) {
        if (!root) return 0;
        count ^= 1 << (root->val - 1);
        int res = dfs(root->left, count) + dfs(root->right, count);
        if (root->left == root->right && (count & (count - 1)) == 0) res++;
        //--------------------------------------^--THIS SECTION-----
        count ^= 1 << (root->val - 1);
        return res;
    }

Solution

  • count & (count - 1) == 0
    

    If count is a power of 2, this statement is true.

    Example: Count = 8

    00001000 = 8
    &
    00000111 = (8-1) = 7 
    ------------
    00000000 = 0