- 浏览: 174500 次
- 性别:
- 来自: 济南
文章分类
最新评论
这篇文章介绍通过位运算求解子集,反转二进制数,判断是否为2的幂等。
1,Number of 1 Bits
给定一个无符号的整数,输出它包含1的个数。
通过右移,依次与1位与,得到1的个数。 代码如下:
2,Subsets
给定一个没有重复元素的数组,输出所有的子集。
例如:给定nums[] = {1,2,3}
输出:[[3], [1], [2], [1,2,3], [1,3],[2,3],[1,2],[] ]
我们知道长度为n的集合,子集的个数为2的n次方个,我们通过0到2^n - 1正好可以表示子集的状态,具体代码如下:
3,Reverse Bits
给定一个无符号整数n,将它的二进制序列反转。
我们每次取n的最后一位,然后再通过左移,得到最终结果。 代码如下:
4,Bitwise AND of Numbers Range
给定一个范围[m, n],将这个区间所有的数字位与,包括m和n, 0 <= m <= n <= 2147483647,输出最后结果。
例如,给定[5,7],输出:4
进行位与操作,位上有一个0,那么这个位置上肯定为0,因此我们只要从高位开始比较m和n,只要他们相等的位我们就保留,如果不相等就终止,因为后面肯定全为0。因为0 <= m <= n <= 2147483647,因此要把mask设定为长整型,因为把1左移31位后,如果是int型,最高位为符号位,与题意不符。代码如下:
1,Number of 1 Bits
给定一个无符号的整数,输出它包含1的个数。
通过右移,依次与1位与,得到1的个数。 代码如下:
public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int count = 0; for(int i = 0; i < 32; i++) { if((n >> i & 1) == 1) { count ++; } } return count; } }
2,Subsets
给定一个没有重复元素的数组,输出所有的子集。
例如:给定nums[] = {1,2,3}
输出:[[3], [1], [2], [1,2,3], [1,3],[2,3],[1,2],[] ]
我们知道长度为n的集合,子集的个数为2的n次方个,我们通过0到2^n - 1正好可以表示子集的状态,具体代码如下:
public class Solution { public List<List<Integer>> subsets(int[] nums) { List<Integer> list = new ArrayList<Integer>(); List<List<Integer>> llist = new ArrayList<List<Integer>>(); Arrays.sort(nums); int helper = 1; for(int i = 0; i < Math.pow(2, nums.length); i++) { for(int j = 0; j < nums.length; j++) { if(((i >> j) & helper) == 1) { list.add(nums[j]); } } llist.add(new ArrayList<Integer>(list)); list.clear(); } return llist; } }
3,Reverse Bits
给定一个无符号整数n,将它的二进制序列反转。
我们每次取n的最后一位,然后再通过左移,得到最终结果。 代码如下:
public class Solution { // you need treat n as an unsigned value public int reverseBits(int n) { int result = 0; for(int i = 0; i < 32; i++) { result = result << 1; result |= ((n >> i)& 1); } return result; } }
4,Bitwise AND of Numbers Range
给定一个范围[m, n],将这个区间所有的数字位与,包括m和n, 0 <= m <= n <= 2147483647,输出最后结果。
例如,给定[5,7],输出:4
进行位与操作,位上有一个0,那么这个位置上肯定为0,因此我们只要从高位开始比较m和n,只要他们相等的位我们就保留,如果不相等就终止,因为后面肯定全为0。因为0 <= m <= n <= 2147483647,因此要把mask设定为长整型,因为把1左移31位后,如果是int型,最高位为符号位,与题意不符。代码如下:
public class Solution { public int rangeBitwiseAnd(int m, int n) { int result = 0; long mask = 1L << 31; while(mask > 0) { if((m & mask) == (n & mask)) { result |= (n & mask); } else { break; } mask = mask >> 1; } return result; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 229Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 231You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 347Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 342Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 460Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 524Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 435Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 623Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 434The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 392Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 541Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 378All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 868Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 884Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 559Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 606Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 771Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 741You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 635For a undirected graph with tre ...
相关推荐
python实现: 二进制和运算符 二进制计数设置位 二进制计数尾随零 二进制或运算符 二进制移位 二进制二进制补码 二进制异或运算符 计数 1S 布赖恩·克尼汉方法 计算 1 位数 ... Highest Set Bit
python爱心代码高级python-bit_manipulation.rar
前端大厂最新面试题-bit-manipulation.docx
ruby_使用ruby进行位操作_bit_manipulation
C++、MFC源代码bit_manipulation_undef_type_source
some bit manipulation python codes
A Mathematical Introduction to Robotic Manipulation Richard M. Murray, Zexiang Li and S. Shankar Sastry
idea 插件 StringManipulation 可以对String 进行编码 大小写 去除空格
Manipulation 简单 Bit Manipulation 简单 Recursion, Backtracking 困难 Binary Search 中等 Tree, Depth-first Search 简单 Bit Manipulation 中等 Bit Manipulation 中等 Dynamic Programming 困难 Math, String ...
A Mathematical Introduction to Robotic Manipulation 超清晰完整大字打印版
java a算法的源码 Bit-Manipulation-Algorithms Java Source Code Representation of Bit manipulation Algorithms
Robotic Grasping and Fine Manipulation
Image_manipulation_detection-master.zip
内含缺失软件包,解压至工作空间scr目录下即可
Hogan - Impedance Control: An Approach to Manipulation: Part III-Applications
Data Manipulation with R
Image-manipulation-detection 图片篡改检测项目的训练权重,基于tensorflow1.X。 使用VOC2007数据集生成5000张待训练图像使用VGG16预训练权重,使用GPU进行训练,经过40000迭代,得到的权重文件。 已放入百度网盘,...
Phil Spector Data Manipulation R