【LeetCode868】二进制间距

目录

题目

解法一、双指针

解法二、尾零个数

---

题目

解法一、双指针

int max(int a, int b) { return a > b ? a : b; } int max_gap(unsigned int n) { int prev = -1; int curr = 0; int len = 0; while (n) { if (n & 0x01) { if (prev != -1) len = max(len, curr - prev); prev = curr; } curr++; n >>= 1; } return len; } int binaryGap(int n) { return max_gap(n); }

解法二、尾零个数

int max(int a, int b) { return a > b ? a : b; } int ctz(unsigned int x) { int cnt = 0; if (!(x & 0x0000FFFF)) { cnt += 16; x >>= 16; } if (!(x & 0x000000FF)) { cnt += 8; x >>= 8; } if (!(x & 0x0000000F)) { cnt += 4; x >>= 4; } if (!(x & 0x00000003)) { cnt += 2; x >>= 2; } if (!(x & 0x00000001)) { cnt += 1; x >>= 1; } return cnt; } int max_gap(unsigned int n) { int shift = ctz(n) + 1; int len = 0; n >>= shift; while (n) { shift = ctz(n) + 1; len = max(len, shift); n >>= shift; } return len; } int binaryGap(int n) { return max_gap(n); }