# 试题:位运算

LeetCode试题

# 位运算:简单

#136 只出现一次的数字

思路:使用位异或,相同数字异或为0,0与其他数字异或为本身,异或满足交换律

#169 多数元素

思路:使用摩尔投票法,对数进行增减操作,遇到相同增加,遇到不同减少,次数为0则重置,直到最后一个无法抵消的就是多出来的,也就是多数

#190 颠倒二进制位

思路:使用把数字转换位2进制字符串,再转换位数组,反转之后再解析

#191 位1的个数(汉明重量)

思路:左移,与1,计数,为0跳出

#232 2的幂

思路:判断n大于0 以及 n与-n相与是否为本身。或者对1的个数计数即汉明重量为1。或者使用2 的最大次幂%n===0来判断

#268 缺失数字

思路:使用异或,下标与数字异或,再和length异或,相同数字异或为0,最终没出现的数字无法与下标异或抵消,最后一个数字可以与length抵消

#342 4的幂

思路:满足4的幂,也满足2的幂,且4的幂满足(3+1)^n,即对3取模之后为1

#371 两整数之和

思路:使用异或可以求无进位和,使用与运算可以求各位进位情况,根据无进位与各位进位情况进行递归计算,直到无进位结果

#389 找不同

思路:思路同268,把字符转成编码,进行字符异或,最终没能异或为0的字符就是添加字符,再转码

#401 二进制手表(回溯)

思路:使用回溯找出所有可能

#405 数字转换为十六进制数

思路:转为二进制,然后再根据4位计算一位十六进制,再无符号右移4位,直到为0。字母可以使用编码或者数组

#461 汉明距离(对应位不同的位数)

思路:2各数异或之后二进制1的个数即为汉明距离

#476 数字的补数

思路:转成二进制,按位取反

#693 交替位二进制数

思路:思路类似,先计算有效位即需要移动的次数,再根据相邻2位判断,使用右移取最低位比较,一个移n位一个移n-1位

#762 二进制表示中质数个数计算置位

思路:本质上还是求区间内的汉明重量,再而就是求质数,以及汉明重量满足质数的个数

#784 字母大小写全排列

思路:使用回溯双递归,对大小写分别递归

#1290 二进制链表转整数

思路:根据链表循环,每次与节点值相或,再左移一位,直到节点为null

#1342 将数字编程0的操作次数

思路:使用循环停止条件为num为0,如果能被2整除就右移2位,否则-1

#1486 数组异或操作

思路:循环,累异或

上次更新: 2020-8-22 21:22:03