位运算介绍和使用

发表于 更新于 分类于 本文字数： 609 阅读时长 ≈ 4 分钟
计算机中的位运算的概念和使用的记录。

背景

刷算法题的时候刷到了关于位运算的题目，之前学习数字逻辑编程语言也学过，但是没什么印象，在算法题中位运算有时候倒是一个优化的手段(也是装x技巧( •̀ ω •́ )✧)，故整理记录下。

位运算操作符

  • & 与
  • | 或
  • ~ 非
  • ^ 异或 1^1 = 0, 1^0 = 1, 0^1 = 1, 0^0 = 0
  • >> 右移 1>>3，1向右移3位(记忆技巧：>指向右方向，也就说把二进制序列往右移，变小)
  • << 左移

位运算操作的基础

位运算各种操作，都是基于二进制的。想要深入了解位运算的各种操作的详细运算过程，最简单的就是把两个数转成二进制。说到二进制，那就得提下计算机中的原码，反码，补码，建议了解下下面这篇文章，有利于理解位运算操作符。 文献：原码, 反码, 补码 详解

各种操作符常用的场景

  • & 可以用来判断数的奇偶性。举个栗子：

    1
    2
    3
    4
    5
    6
    if ((a & 1) == 0) {
        // a 为奇数
    }
    else {
        // a 为偶数
    }

  • 同理 | 也可以用来判断数的奇偶性。

  • ^可以用来交换两个数，也可以用来确定数组序列中唯一不重复的数。举个栗子：

    1
    2
    3
    4
    5
    // 交换两个数a,b
    int a,b;
    a = a^b;
    b = a^b;
    a = a^a;

  • >>或者<<移位操作可以用来代替除2或者乘2操作，提高效率。

相关练习题目