LeetCode 题解

积跬步，至千里。

下一个数

分类：程序员面试金典题解 标签： 位运算 发布于：2020-05-20 ID：5.04

题目描述

来源于 https://leetcode-cn.com/

下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。

示例1:

 输入：num = 2（或者0b10）
 输出：[4, 1] 或者（[0b100, 0b1]）

示例2:

 输入：num = 1
 输出：[2, -1]

提示:

  1. num的范围在[1, 2147483647]之间；
  2. 如果找不到前一个或者后一个满足条件的正数，那么输出 -1。

解法：

设 num = 1,837,591,841，num 的二进制表示如下：

110 1101 1000 0111 0110 1101 0010 0001‬

把它视为一个数组，下一个较大的数的各个位，就是这个数组的下一个排列组合。

而前一个较小的数，就是这个数组的前一个排列组合。寻找前一个排列组合，只需要修改一下比较函数即可。

寻找下一个排列组合的算法可以参考：leetcode 31 题。

class Solution {
public:
    vector<int> findClosedNumbers(int num) {
        return {next(num) , prev(num)};
    }

    int next(int num){
        vector<char> bits;
        for(int i=31;i>=0;i--){
            bits.push_back(bit(num, i));
        }

        if(next_permutation(bits.begin(), bits.end())){
            int n = 0;
            for(int i=0;i<bits.size();i++){
                if(bits[i] == 1){
                    n = set_bit(n, 31-i, 1);
                }
            }
            return n;
        }else{
            return -1;
        }
    }

    int prev(int num){
        vector<char> bits;
        for(int i=31;i>=0;i--){
            bits.push_back(bit(num, i));
        }
        auto comp = [](int a, int b){
            return a > b;
        };
        if(next_permutation(bits.begin(), bits.end(), comp)){
            int n = 0;
            for(int i=0;i<bits.size();i++){
                if(bits[i] == 1){
                    n = set_bit(n, 31-i, 1);
                }
            }
            return n;
        }else{
            return -1;
        }
    }

    int bit(int num, int i){
        if(num & (1 << i)){
            return 1;
        }else{
            return 0;
        }
    }

    int set_bit(int num, int i, int val){
        if(val){
            return num | (1 << i);
        }else{
            return num & ~(1 << i);
        }
    }
};