Algorithm

Bit Twiddling Hacks Summary This note summarizes practical techniques from Bit Twiddling Hacks. It follows the same style as common-algorithm-patterns.md: each topic has Explanation + C++ Framework. 0) Preconditions and Portability Explanation Bit hacks are highly sensitive to integer representation and shift semantics: Prefer unsigned fixed-width types like uint32_t / uint64_t. Right-shifting negative signed values is implementation-defined. Be careful with overflow-prone expressions such as x - y. Code Framework 1 2 3 4 5 6 7 #include <bit> #include <cstdint> #include <limits> using u32 = uint32_t; using u64 = uint64_t; using i32 = int32_t; 1) Sign and Opposite-Sign Detection Explanation Sign extraction is often normalized to -1 / 0 / 1. Two values have opposite signs when their sign bits differ. Code Framework 1 2 3 4 5 6 7 int sign3(int x) { return (x > 0) - (x < 0); // -1 / 0 / 1 } bool oppositeSigns(int x, int y) { return (x ^ y) < 0; } 2) Branchless abs / min / max Explanation Useful when branch misprediction is expensive, but always benchmark against normal standard-library versions first. ...

Common Algorithm Patterns Each pattern has only two parts: Explanation + Code Framework. 1) Framework Thinking (Traversal First) Explanation Most problems are traversal problems in disguise: arrays, linked lists, trees, graphs. Identify the data structure first, then pick traversal order, then fill business logic into the skeleton. Code Framework 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <vector> using namespace std; struct ListNode { int val; ListNode* next; }; struct TreeNode { int val; TreeNode* left; TreeNode* right; }; void processValue(int x) { // TODO: business logic (void)x; } void traverseArray(const vector<int>& nums) { for (int i = 0; i < (int)nums.size(); ++i) { processValue(nums[i]); } } void traverseList(ListNode* head) { for (ListNode* p = head; p != nullptr; p = p->next) { processValue(p->val); } } void traverseTree(TreeNode* root) { if (root == nullptr) return; // Pre-order processValue(root->val); traverseTree(root->left); traverseTree(root->right); // Post-order } 2) Binary Search (Shrink Search Space) Explanation Use binary search when monotonicity exists. The key is consistency: interval definition + boundary update rules. ...

A colleague dropped some code on me and asked why applying a semi-transparent mask to images was so slow. Apparently it was written by a “strong algorithm engineer” from another team. Here it is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 # -*- coding: utf-8 -*- import numpy as np import os import cv2 def put_mask(img_path, output_fold): image = cv2.imread(r'E:\testdemo.jpg') bbox1 = [72, 41, 208, 330] bbox2 = [100, 80, 248, 334] zeros1 = np.zeros((image.shape), dtype=np.uint8) zeros2 = np.zeros((image.shape), dtype=np.uint8) zeros_mask1 = cv2.rectangle(zeros1, (bbox1[0], bbox1[1]), (bbox1[2], bbox1[3]), color=(0, 0, 255), thickness=-1) zeros_mask2 = cv2.rectangle(zeros2, (bbox2[0], bbox2[1]), (bbox2[2], bbox2[3]), color=(0, 255, 0), thickness=-1) zeros_mask = np.array((zeros_mask1 + zeros_mask2)) try: alpha = 1 # opacity of the original image beta = 0.5 # opacity of the mask layer gamma = 0 # blend original image with mask mask_img = cv2.addWeighted(image, alpha, zeros_mask, beta, gamma) cv2.imwrite(os.path.join(output_fold, 'mask_img.jpg'), mask_img) except: print('error') put_mask(img_path='107.jpg', output_fold=r'E:\output') My first reaction: this is pretty careless. Python is easy to write — that’s true — but that doesn’t mean anything goes. ...