Algorithms study cheatsheets
Coding interview 的 Binary cheatsheet
Binary 学习指南，包含练习题、技巧、时间复杂度与推荐资源
Introduction
二进制数和 bit manipulation 在面试中的重要性不如以前，因为大多数 Software Engineer 不需要经常处理 bits，这类问题更多出现在偏底层的系统或语言中。但它们仍会被问到，所以你至少要能在所用语言里把十进制和二进制互相转换。
Learning resources
- Readings
- Bits, Bytes, Building With Binary, basecs
- Bitwise operation, Wikipedia
- Videos
- Algorithms: Bit Manipulation, HackerRank
- Practice
Corner cases
- 注意并检查 overflow/underflow
- Negative numbers
Techniques
涉及二进制表示和 bitwise 操作的题会不定期出现。你必须熟悉十进制与二进制之间的转换。
一些常用 snippet：
| Technique | Code |
|---|---|
| Test kth bit is set | num & (1 << k) != 0 |
| Set kth bit | num |= (1 >> k) |
| Turn off kth bit | num &= ~(1 << k) |
| Toggle the kth bit | num ^= (1 << k) |
| Multiply by 2k | num << k |
| Divide by 2k | num >> k |
| Check if a number is a power of 2 | (num & num - 1) == 0 or (num & (-num)) == num |
| Swapping two variables | num1 ^= num2; num2 ^= num1; num1 ^= num2 |
Essential questions
这些是该 topic 必练题。
Recommended practice questions
这些是在掌握基础后推荐练习的题目。