Clever Bitlogic with Rust
Intuition\nThe core idea here is to use the "+ 1" to cascade carry bits and restore a the highest bit of the original number it can. \n\n# Approach\n\nI\'ve don
# Intuition\nThe core idea here is to use the "+ 1" to cascade carry bits and restore a the highest bit of the original number it can. \n\n# Approach\n\nI\'ve done my best to detail the workings in the code + debug logging.\nFirst off, if `num` is even, there\'s no way to encode it as `x | (x + 1)`. \n- If `x` is even, then `x + 1` is odd and their `|` is odd.\n- If `x` is odd, then `x + 1` is even and their `|` is odd.\nTherefor, all even numbers are immediately encoded as `-1` aka "cannot be done".\n\nNow we know that all other `num` values are odd, so they have one or more trailing ones in their binary representation:\n```\nnum => binary          => tail\n  3 => 0b0011          => 0b11\n  5 => 0b0101          => 0b1\n  7 => 0b0111          => 0b111  \n911 => 0b11_1101_1111  => 0b01_1111\n```\n\nWe want to abuse that chain, to get get `ans[i] + 1` to always be a bit that\'s set in `num`, so that the `|` works. We do this by taking each "tail" and shortening it by one. Now when that tail is incremented, it carries into the highest bit of that initial tail.\n\nUsing `num=7`:\n- `7` in binary is `0b0111`\n- The tail is `0b111`, and there\'s nothing after the tail\n- We\'ll find the high bit of the tail by shifting right by 1 and incrementing to cause a carry:\n    - `0b0111 >> 1 == 0b0011`\n    - `0b0011 + 1 == 0b0100`\n    - Which we see matches the `0b0111` tail we started with.\n- Now subtract off this high bit from our original number.\n- `7 - 0b0100 == 0b0111 - 0b0100 == 0b0011 == 3` \n- This is our answer for `7`: it should be encoded as `3`.\n- We can confirm by redoing our `ans[i]` math:\n    - `3 + 1 == 4, 3 | 4 == 0b0011 | 0b0100 == 0b0111 == 7`\n\nThe code does this concisely with:\n```rust []\n// p is from `nums`\nlet half_p: i32 = p >> 1;\nreturn p - (1 << half_p.trailing_ones());\n```\n\nNote: If you don\'t use the full tail here, you get answers that work but they are not minimal! Using the full is necessary to get the smallest answer. On some observation, numbers with short enough tails don\'t make this distinction. (Try the above with `num=5`, for example.)\n\nI recommend doing a few by hand and comparing the debug output in the code below to better understand what\'s happening. It\'s a very clever trick I saw in a different write up here, but without much explanation. I hope this adds more context. :)\n\n# Complexity\n- Time complexity: $$O(n)$$, a fixed number of bit ops (all $$O(1)$$) per num in `nums`.\n    - Note: If you do not have access to a hardware "count trailing ones" intrinsic, then this complexity worsens. Most CPUs support this, but how it gets exposed into higher langauges varies.\n    Worst case, you need to write a $$O(b)$$ loop where $$b$$ is the number of bits in your integer *value*. Since the problem bounds this to ~1000, $$b$$ is never more than 10.\n- Space complexity: $$O(n)$$, a fixed amount of space per num in `nums`.\n\n# Code\n```rust []\nimpl Solution {\n    pub fn min_bitwise_array(nums: Vec<i32>) -> Vec<i32> {\n        nums.into_iter().map(min_bitwise).collect()\n    }\n}\n\nfn min_bitwise(p: i32) -> i32 {\n    if p % 2 == 0 {\n        // (p | (p+1)) is always odd, so no even number can be expressed this way.\n        -1\n    } else {\n        // The core idea here, is to find a run of 1s in the binary reprentation of \'p\'.\n        // We\'ll then subtract off the top 1 in that string from \'p\'.\n        // Any chain will give us a correct encoding, but we want the minimum value stored so that means the longest chain we can find.\n        // Because we\'ll add 1 to this chain, we need it to be the longest chain of 1s from the least significant bit.\n        //  Consider 991:\n        //      991 = 0b01111011111\n        //                    ^___^ is our chain.\n        //  We want to subtract off the top of the chain, but one shorter so the +1 restores that upper bit. We\'ll use:\n        //      991 >> 1 = 0b00111101111\n        //  Now we count the lower ones (4 long), and know the value to subtract out of \'p\':\n        //      1 << 4\n        //  This ultimately lets the (ans[i] + 1) logic turn back into that upper bit, and get OR\'d into \'ans[i]\' and restore \'p\'!\n        //\n        // Fail a test to see detailed output:\n        if cfg!(debug_assertions) {\n            let x = "    ";\n            let xx = "        ";\n            let half_p = p >> 1;\n            let hf_ct1 = half_p.trailing_ones();\n\n            println!("min_bitwise({p}):");\n            println!("{x}Consider:");\n            println!("{x}    {p:>3} = 0b{p:011b}");\n            println!("{x}          {} trailing ones", p.trailing_ones());\n\n            println!("{x}Shift right once:");\n            println!("{x}    {half_p:>3} = 0b{half_p:011b}");\n            println!("{x}          {} trailing ones", hf_ct1);\n\n            println!();\n            println!("{xx}(1 << {hf_ct1}) = 0b{:011b}", 1 << hf_ct1);\n            println!("{x}         {p:>3} = 0b{p:011b}");\n\n            println!("{x}Then");\n            println!("{xx}{p} - (1 << {hf_ct1}) == 0b{:011b}", p - (1 << hf_ct1));\n\n            println!("{x}and to piece it back together:");\n            println!("{xx}0b{0:011b} ({p} - (1 << {hf_ct1}))", p - (1 << hf_ct1));\n            println!("{x}  + 0b{0:011b} ({0})", 1);\n            println!("{x}  ----------");\n            println!(\n                "{xx}0b{0:011b} ({p} - (1 << {hf_ct1}) + 1)",\n                p - (1 << hf_ct1) + 1\n            );\n            println!("{x}  | 0b{0:011b} ({0})", p);\n            println!("{x}  ----------");\n            let sum = (p - (1 << hf_ct1)) | (p - (1 << hf_ct1) + 1);\n            println!("{x}    0b{0:011b} ({0})", sum);\n\n            println!();\n            println!();\n        }\n\n        let half_p = p >> 1;\n        p - (1 << half_p.trailing_ones())\n    }\n}\n```
['Bit Manipulation', 'Rust']