小编点评

**算法函数** * `getBinary(int num)`：返回二进制形式的 32 位整数。 * `getNumBits(int range)`：返回在 [0, range) 中 0 出现的数的个数。 **数据结构** * `NumArray`：使用前缀和数组加速求区间和。 **其他工具函数** * `getNeedBits(int range)`：计算 0 ~ range 中 0 的概率。 * `randToPow2()`：返回 [0, 1) 中随机一个数的概率。

正文

算法和数据结构学习中的一些小的工具函数

作者：Grey

原文地址：

博客园：算法和数据结构学习中的一些小的工具函数

CSDN：算法和数据结构学习中的一些小的工具函数

提取一个数二进制最右侧的 1

比如二进制为：0100 0001 0001 1011 0001 0001 1001 1000

最右侧的1为： 0000 0000 0000 0000 0000 0000 0000 1000

num & (-num)

或

num & (~num + 1)

打印一个 32 位整数的二进制形式

public static String getBinary(int num) {
    StringBuilder sb = new StringBuilder();
    for (int i = 31; i >= 0; i--) {
        sb.append(((1 << i) & num) == 0 ? "0" : "1");
    }
    return sb.toString();
}

前缀和数组加速求区间和

在数组不可变的情况下，可以使用前缀和数组加速求区间和，描述见：leetcpde 0303 range sum query immutable

    class NumArray {
        int[] preSum;

        public NumArray(int[] nums) {
            preSum = new int[nums.length];
            preSum[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                preSum[i] = nums[i] + preSum[i - 1];
            }
        }

        public int sumRange(int left, int right) {
            if (left == 0) {
                return preSum[right];
            }
            return preSum[right] - preSum[left - 1];
        }
    }

注：前缀和只适合数组不可变情况下加速求区间和，如果数组可变，则需要使用线段树或者树状数组来解决这个问题。

要表示 0 ~ range 需要几个二进制位

public static int getNeedBits(int range) {
    int num = 1;
    while ((1 << num) - 1 < range) {
        num++;
    }
    return num;
}

将[0,x)中的数出现的概率调整成\(x^2\)

public static double randToPow2() {
    return Math.max(Math.random(), Math.random());
}

说明：Math.random()表示的是[0,1)区间中任意一个数 X 的概率是 X。

持续更新中

更多

算法和数据结构笔记