打印kth一个数的最低有效位有大量我们知道,每个数字都可以用数字的形式表示,数字格式可以是二进制、十进制、十六进制、八进制等任何形式。如果我们用位的形式表示这个数字,那么最左边的数字称为最高位,最右边的数字称为最低位。 我们知道,最左边的位的值较高,因为它乘以了其基础值的最高次幂,所以它在确定值方面最有意义。 最右边的数字乘以基础值的零次方,因此它在值的计算中贡献最小。这就是为什么它被称为最低有效位(LSB)。 例如: 以数字12为例,在二进制格式中;我们可以用0和1的形式表示12。 所以12的二进制表示将是:1100 12的最高有效位是1,最低有效位是0。 现在,我们可以找到任何最低有效位如果我们有任何数字的二进制表示。 方法1:我们会得到一个整数和一个代表k的数,如果我们想要一个kth最低有效位,然后我们将得到这个特定数字的二进制表示形式并将它存储到一个数组中,然后从右边k开始th数组的元素将表示kth最低有效位。 Java代码: 输出: ![]() ![]() 解释 在上面的例子中,我们使用一个大小为32的数组来存储数字n的二进制表示“getBinaryBits”将使用除法以二进制格式存储表示数字的二进制。 例如,我们取n=27 k=2。 所以27在二进制表示中是这样的 ![]() 所以k=2意味着第二个最低有效位出现在倒数第二个索引处。 在上面的代码中,我们使用额外的空间来存储比特,所以时间和空间复杂度将是O(32),这几乎是恒定的。 方法2:另一种方法是我们将位向右移动k-1次。 正如我们所知,每次移动一个元素时,最低有效位就会消失,因此通过执行k-1次这个操作,我们将从左侧删除前k-1位,最右侧的位表示最低有效位。 现在,为了确定比特是1还是0,我们将检查数字是否为偶数。那么,最右边的位是0。否则为1。 Java代码: 以上代码的时间复杂度为O (K),空间复杂度是O(1)。 方法3:这个方法说的是,当kth位为1,其他位为0。现在,如果这个数字是位与n,如果结果是零,那么它表示kthn的位是零。否则,kthn的位是1。 得到含有k的数th一个为0,另一个为0,我们将左移1 (k-1)次。 Java代码: 解释: 设n=16, k=3,所以旋转1 (k-1)或者我们可以说左两次。 ![]() 因此,我们旋转k 2次,并在n=16的情况下进行位与运算,我们得到的结果是0。所以n的第三位肯定是零。 如果我们讨论时间复杂度,那么它也是恒定的时间和空间复杂度也是恒定的。 时间复杂度:O (1) 空间复杂度:O (1)
下一个话题
两个用链表表示的数相加
|