打印数字的第k个最低有效位

最低有效位

我们知道，每个数字都可以表示成数字的形式，数字的格式可以是任何形式，如二进制、十进制、十六进制、八进制等。如果我们用比特来表示数字，那么最左边的数字称为最高有效位，最右边的数字称为最低有效位。

我们知道，最左边的比特具有更高的值，因为它乘以其基值的最高幂，所以在确定值方面具有最重要的意义。

最右边的数字乘以基值零次幂，因此在计算值方面贡献最小。这就是为什么它被称为最低有效位（LSB）。

例如

让我们以数字12为例，在二进制格式下；我们可以用0和1来表示12。

所以12的二进制表示是：1100

12的最高有效位是1，最低有效位是0。

现在，如果我们有了任何数字的二进制表示，我们就可以找到任何一个最低有效位。

方法 1

我们将给出一个整数n和一个表示k的数字。所以，如果我们想要第k个最低有效位，我们只需获取该特定数字的二进制表示并将其存储到数组中，然后从数组的右侧开始，第k个元素将代表第k个最低有效位。

Java 代码

输出

说明

在上面，我们使用了一个大小为32的数组来存储数字n的二进制表示。函数'getBinaryBits'将使用除法方法以二进制格式存储表示数字的二进制。

例如，我们取n=27，k=2。

所以27的二进制表示如下：

所以k=2意味着第2个最低有效位是1，它位于倒数第二个索引处。

在上面的代码中，我们使用了额外的空间来存储比特，所以时间和空间复杂度是O(32)，接近常数。

方法 2

另一种方法是我们将比特向右移动k-1次。

我们知道，每次移动一个元素时，最低有效位就会消失，所以通过执行这个操作k-1次，我们将从左侧移除前k-1个比特，而最右边的比特将代表我们的最低有效位。

现在，要确定比特是1还是0，我们将检查数字是否为偶数。如果是偶数，则最右边的比特是0。否则，它是1。

Java 代码

上述代码的时间复杂度为O(K)，空间复杂度为O(1)。

方法 3

这种方法说的是，我们将得到一个数字，其中第k位为1，其他位为0。现在，如果将该数字与n进行按位与运算，如果结果为零，则表示n的第k位为零。否则，n的第k位为一。

要获得第k位为1，其他位为0的数字，我们将1左移(k-1)次。

Java 代码

说明

让我们取n=16，k=3，所以我们将1左移(k-1)次，或者说两次。

所以，我们将k左移了2次，并与n=16进行按位与运算，得到结果为0。因此，n的第3位肯定为零。

如果谈论时间复杂度，那么它也是常数时间，空间复杂度也是常数。

时间复杂度： O(1)

空间复杂度：O(1)