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;
}
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