面试题 05.08. 绘制直线

题目

绘制直线。有个单色屏幕存储在一个一维数组中，使得32个连续像素可以存放在一个 int 里。屏幕宽度为w，且w可被32整除（即一个 int 不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数，绘制从点(x1, y)到点(x2, y)的水平线。

给出数组的长度 length，宽度 w（以比特为单位）、直线开始位置 x1（比特为单位）、直线结束位置 x2（比特为单位）、直线所在行数y。返回绘制过后的数组。

示例1:
输入：length = 1, w = 32, x1 = 30, x2 = 31, y = 0
输出：[3]
说明：在第0行的第30位到第31为画一条直线，屏幕表示为[0b000000000000000000000000000000011]

示例2:
输入：length = 3, w = 96, x1 = 0, x2 = 95, y = 0
输出：[-1, -1, -1]

题解

public int[] drawLine(int length, int w, int x1, int x2, int y) {
    int[] result = new int[length];
    // 数字像素长度 屏幕宽度几个数字
    int len = 32, width = w / len;

    // 保证x1小于x2
    if (x1 > x2) {
        x1 ^= x2;
        x2 ^= x1;
        x1 ^= x2;
    }

    // 根据直线起止位置找到横跨的数字位置
    for (int j = x1 / len; j < (x2 / len + (x2 % len == 0 ? 0 : 1)); j++) {
        // 数字开始像素索引
        int begin = j * len;
        // 数字结束像素索引
        int end = (j + 1) * len - 1;
        // 若包含一个数字的开始符号位像素 则是负数 否则为正数
        if (x1 <= begin) {
            // 区分是正数还是负数
            result[y * width + j] = -1;
            // 由低位到高位去0的位数
            int bit = end - Math.min(x2, end);
            // 去掉低位的0
            for (int i = 0; i < bit; i++) {
                result[y * width + j] &= (result[y * width + j] - 1);
            }
        } else {
            // 需要左移动位数 确定最低位1
            // 若终点像素大于当前数字最大像素则从1开始 否则左移
            result[y * width + j] = 1 << (x2 >= end ? 0 : end - x2);
            int bit = Math.min(x2, end) - Math.max(x1, begin);
            for (int i = 0; i < bit; i++) {
                // 高位加1
                result[y * width + j] |= (result[y * width + j] << 1);
            }
        }
    }

    return result;
}